Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
Zonghao Gu, George L. Nemhauser, Martin W. P. Savelsbergh
INFORMS Journal on Computing · 1999 · Volume 11 · Issue 1
Abstract
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.
Keywords
integer programming, cutting plane, complexity of separation, separation algorithms
Enable JavaScript for citation tools and additional paper interactions.