The complexity of cover inequality separation

D. Klabjan*, G. L. Nemhauser, C. Tovey

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)35-40
Number of pages6
JournalOperations Research Letters
Volume23
Issue number1-2
DOIs
StatePublished - Aug 1 1998

Keywords

  • Cover inequalities
  • Integer programming
  • Separation problem

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The complexity of cover inequality separation'. Together they form a unique fingerprint.

Cite this