Optimization Online


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

Adam N. Letchford (a.n.letchford***at***lancaster.ac.uk)
Georgia Souli (g.souli***at***lancaster.ac.uk)

Abstract: 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.

Keywords: knapsack problems, lifted cover inequalities, polyhedral combinatorics

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: 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.


Entry Submitted: 08/22/2018
Entry Accepted: 08/24/2018
Entry Last Modified: 06/10/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society