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.
Primal separation algorithms / Letchford A.N.; Lodi A.. - In: 4OR. - ISSN 1619-4500. - STAMPA. - 1:3(2003), pp. 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.
