Journal
MATHEMATICAL PROGRAMMING
Volume 124, Issue 1-2, Pages 69-91Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-010-0359-5
Keywords
Integer programming; Knapsack problems; Cutting planes
Categories
Funding
- EPSRC [EP/D072662/1, EP/F033613/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/F033613/1, EP/D072662/1] Funding Source: researchfish
Ask authors/readers for more resources
Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack polytope itself. Extensive computational results, on MIPLIB and OR Library instances, show the strengths and limitations of the inequalities and algorithms considered.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available