| The Complexity Of Cover Inequality Separation (1998) | |||||||||||||||
Abstract | |||||||||||||||
| . Crowder et al. [1] conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special case is solvable in linear time. Keywords: Integer programming, Cover inequalities, Separation problem 1 This research was supported by US Army Research Office DAAH04-94-G-0017 and NSF Grant No. DMI9700285. 1. Introduction Separation problems for linear programs with an exponential number of constraints arise in polyhedral approaches to combinatorial optimization problems. These separation problems frequently are special cases of NP-hard problems such as knapsack or max-cut. The special cases arise because of the restricted inputs, which come from the solutions of relaxed linear programs. An example is the separation problem for cover inequalities for binary integer programs introduced by Crowder et al. [1] more than 10 years ago. The following is a quote from their paper that enlightens... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||