Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

0.00 Avg rating0 Votes
Article ID: iaor20091385
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 254
End Page Number: 261
Publication Date: May 2008
Journal: Discrete Optimization
Authors: ,
Keywords: knapsack problem
Abstract:

Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.

Reviews

Required fields are marked *. Your email address will not be published.