| Article ID: | iaor20119271 |
| Volume: | 39 |
| Issue: | 5 |
| Start Page Number: | 301 |
| End Page Number: | 304 |
| Publication Date: | Sep 2011 |
| Journal: | Operations Research Letters |
| Authors: | Letchford Adam N, Schulz Andreas S, Pokutta Sebastian |
| Keywords: | cutting plane algorithms |
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.