Given an integer polyhedron PI ⊂ ℝn, an integer point &xmacr; ∈ 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 &xmacr;. 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.
