Home > Research > Publications & Outputs > On the membership problem for the {0, 1/2}-closure

Electronic data

Links

Text available via DOI:

View graph of relations

On the membership problem for the {0, 1/2}-closure

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
Close
<mark>Journal publication date</mark>09/2011
<mark>Journal</mark>Operations Research Letters
Issue number5
Volume39
Number of pages4
Pages (from-to)301-304
Publication StatusPublished
Early online date29/07/11
<mark>Original language</mark>English

Abstract

In integer programming, {0,1/2}-cuts are Gomory–Chvátal cuts that can be derived from the original linear system by using coefficients of value 0 or 1/2 only. The separation problem for {0,1/2}-cuts is strongly NP-hard. We show that separation remains strongly NP-hard, even when all integer variables are binary.