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.
No takes yet. Share an insight, caveat, or question.
Gu et al. (1999) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: