Publication year: 2011
Source: Operations Research Letters, Volume 39, Issue 5, September 2011, Pages 301-304
Adam N. Letchford, Sebastian Pokutta, Andreas S. Schulz
In integer programming,-cuts are Gomory–Chvátal cuts that can be derived from the original linear system by using coefficients of valueoronly. The separation problem for-cuts is strongly NP-hard. We show that separation remains strongly NP-hard, even when all integer variables are binary.
Highlights
► Zero-half cuts are a class of cutting planes for integer programming problems. ► They form a subclass of the well-known Gomory–Chvátal cuts. ► To use them computationally, a separation algorithm is needed. ► It is known that the separation problem is NP-hard in general. ► We show that it remains NP-hard even when all variables are binary.