| Affiliation: | (1) Department of Management Science, Lancaster University, LA1 4YW Lancaster, England;(2) D.E.I.S., University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy |
| Abstract: | Given an integer polyhedron  , an integer point  , and a point  , the primal separation problem is the problem of finding a linear inequality which is valid for P I , violated by x *, and satisfied at equality by  . 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.Received: November 2002, Revised: March 2003, |
