Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Primal separation algorithms
AU - Letchford, A. N.
AU - Lodi, A.
PY - 2003/10
Y1 - 2003/10
N2 - Given an integer polyhedron P ⊂ R^n, an integer point x in P, and a point x* in R^n \ P, the primal separation problem is the problem of finding a linear inequality which is valid for P, violated by x*, and satisfied at equality by x. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.
AB - Given an integer polyhedron P ⊂ R^n, an integer point x in P, and a point x* in R^n \ P, the primal separation problem is the problem of finding a linear inequality which is valid for P, violated by x*, and satisfied at equality by x. The primal separation problem plays a key role in the primal approach to integer programming. In this paper we examine the complexity of primal separation for several well known classes of inequalities for various important combinatorial optimization problems, including the knapsack, stable set and travelling salesman problems.
KW - integer programming
KW - cutting planes
KW - separation
KW - primal algorithms
KW - knapsack problem
KW - stable set problem
KW - travelling salesman problem
U2 - 10.1007/s10288-003-0012-8
DO - 10.1007/s10288-003-0012-8
M3 - Journal article
VL - 1
SP - 209
EP - 224
JO - 4OR: A Quarterly Journal of Operations Research
JF - 4OR: A Quarterly Journal of Operations Research
SN - 1619-4500
IS - 3
ER -