On Lifted Cover Inequalities: A New Lifting Procedure with Unusual Properties

Lifted cover inequalities are well-known cutting planes for 0-1 linear programs. We show how one of the earliest lifting procedures, due to Balas, can be significantly improved. The resulting procedure has some unusual properties. For example, (i) it can yield facet-defining inequalities even if the given cover is not minimal, (ii) it can yield facet-defining inequalities that cannot be obtained by standard lifting procedures, and (iii) the associated superadditive lifting function is integer-valued almost everywhere.


Appeared as: A.N. Letchford & G. Souli (2019) On lifted cover inequalities: a new lifting procedure with unusual properties. Oper. Res. Lett., 47(2), 83-87.