Given an integer polyhedron PI ⊂ ℝn, an integer point x̄ ∈ PI, and a point x* ∈ ℝn \ PI, the primal separation problem is the problem of finding a linear inequality which is valid for PI, 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. © 2003 Springer-Verlag Berlin/Heidelberg.
Letchford A.N., Lodi A. (2003). Primal separation algorithms. 4OR, 1(3), 209-224 [10.1007/s10288-003-0012-8].
Primal separation algorithms
Lodi A.
2003
Abstract
Given an integer polyhedron PI ⊂ ℝn, an integer point x̄ ∈ PI, and a point x* ∈ ℝn \ PI, the primal separation problem is the problem of finding a linear inequality which is valid for PI, 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. © 2003 Springer-Verlag Berlin/Heidelberg.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
