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: | Easton Todd, Hooker Kevin |
Keywords: | knapsack problem |
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.