Lifted cover inequalities for 0-1 integer programs: Complexity

Authors
Gu, ZH Nemhauser, GL Savelsbergh, MWP
Citation
Zh. Gu et al., Lifted cover inequalities for 0-1 integer programs: Complexity, INFORMS J C, 11(1), 1999, pp. 117-123
Citations number
21
Categorie Soggetti
Computer Science & Engineering
Journal title
INFORMS JOURNAL ON COMPUTING
ISSN journal
10919856 → ACNP
Volume
11
Issue
1
Year of publication
1999
Pages
117 - 123
Database
ISI
SICI code
1091-9856(199924)11:1<117:LCIF0I>2.0.ZU;2-O
Abstract
We investigate several complexity issues related to branch-and-cut algorith ms for 0-1 integer programming based on lifted-cover inequalities (LCIs). W e show that given a fractional point, determining a violated LCI over all m inimal covers is NP-hard. The main result is that there exists a class of 0 -1 knapsack instances for which any branch-and-out algorithm based on LCls has to evaluate an exponential number of nodes to prove optimality.