Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142616 | Operations Research Letters | 2011 | 4 Pages |
Abstract
⺠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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Adam N. Letchford, Sebastian Pokutta, Andreas S. Schulz,