Crowder et al. (Oper. Res. 31 (1983) 803-834) 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.
- Cover inequalities
- Integer programming
- Separation problem
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics