| Article ID: | iaor2000989 |
| Country: | United States |
| Volume: | 11 |
| Issue: | 1 |
| Start Page Number: | 117 |
| End Page Number: | 123 |
| Publication Date: | Dec 1999 |
| Journal: | INFORMS Journal On Computing |
| Authors: | Nemhauser George L., Gu Zonghao, Savelsbergh Martin W.P. |
| Keywords: | programming: integer |
We investigate several complexity issues related to branch-and-cut algorithms for 0–1 integer programming based on lifted-cover inequalities (LCIs). We show that given a fractional point, determining a violated LCI over all minimal covers is NP-hard. The main result is that there exists a class of 0–1 knapsack instances for which any branch-and-cut algorithm based on LCIs has to evaluate an exponential number of nodes to prove optimality.