On Lifted Cover Inequalities: A New Lifting Procedure with Unusual Properties
Adam N. Letchford (a.n.letchfordlancaster.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|