DRL*: A hierarchy of strong block-decomposable linear relaxations for 0–1 MIPs Original Research Article

In this paper we introduce DRL*, a new hierarchy of linear relaxations for 0–1 mixed integer linear programs (MIPs), based on the idea of Reformulation–Linearization, and explore its links with the Lift-and-Project (L&P) hierarchy and the Sherali–Adams (RLT) hierarchy. The relaxations of the new hierarchy are shown to be intermediate in strength between L&P and RLT relaxations, and examples are shown for which it leads to significantly stronger bounds than those obtained from Lift-and-Project relaxations. On the other hand, as opposed to the RLT relaxations, a key advantage of the DRL* relaxations is that they feature a decomposable structure when formulated in extended space, therefore lending themselves to more efficient solution algorithms by properly exploiting decomposition. Links between DRL* and both the L&P and RLT hierarchies are furth