TY - JOUR

T1 - Separation algorithms for 0-1 knapsack polytopes

AU - Kaparis, Konstantinos

AU - Letchford, Adam

PY - 2010/7

Y1 - 2010/7

N2 - Valid inequalities for 0-1 knapsack polytopes often prove useful when tacklinghard 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.

AB - Valid inequalities for 0-1 knapsack polytopes often prove useful when tacklinghard 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.

KW - Integer programming

KW - Knapsack problems

KW - Cutting planes

U2 - 10.1007/s10107-010-0359-5

DO - 10.1007/s10107-010-0359-5

M3 - Journal article

VL - 124

SP - 69

EP - 91

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -