The complexity of cover inequality separation

D. Klabjan; G. L. Nemhauser; C. Tovey

doi:10.1016/S0167-6377(98)00025-X

The complexity of cover inequality separation

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

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

29 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 language	English (US)
Pages (from-to)	35-40
Number of pages	6
Journal	Operations Research Letters
Volume	23
Issue number	1-2
DOIs	https://doi.org/10.1016/S0167-6377(98)00025-X
State	Published - 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

Access to Document

10.1016/S0167-6377(98)00025-X

Cite this

@article{5273b629c6f8445ca52f58c0ffa43eea,

title = "The complexity of cover inequality separation",

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.",

keywords = "Cover inequalities, Integer programming, Separation problem",

author = "D. Klabjan and Nemhauser, {G. L.} and C. Tovey",

note = "Funding Information: This research was supported by US Army Research Office DAAH04-94-G-0017 and NSF Grant No. DMI-9700285. ",

year = "1998",

month = aug,

day = "1",

doi = "10.1016/S0167-6377(98)00025-X",

language = "English (US)",

volume = "23",

pages = "35--40",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - The complexity of cover inequality separation

AU - Klabjan, D.

AU - Nemhauser, G. L.

AU - Tovey, C.

N1 - Funding Information: This research was supported by US Army Research Office DAAH04-94-G-0017 and NSF Grant No. DMI-9700285.

PY - 1998/8/1

Y1 - 1998/8/1

N2 - 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.

AB - 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.

KW - Cover inequalities

KW - Integer programming

KW - Separation problem

UR - http://www.scopus.com/inward/record.url?scp=0032131434&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032131434&partnerID=8YFLogxK

U2 - 10.1016/S0167-6377(98)00025-X

DO - 10.1016/S0167-6377(98)00025-X

M3 - Article

AN - SCOPUS:0032131434

SN - 0167-6377

VL - 23

SP - 35

EP - 40

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1-2

ER -

The complexity of cover inequality separation

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this