Abstract
The [Formula presented]-closure of a rational polyhedron {x:Ax≤b} is obtained by adding all Gomory-Chvátal cuts that can be derived from the linear system Ax≤b using multipliers in [Formula presented]. We show that deciding whether the [Formula presented]-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the [Formula presented]-closure derived from Ax≤b is totally dual integral, is strongly NP-hard.
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 16-19 |
Seitenumfang | 4 |
Fachzeitschrift | Operations Research Letters |
Jahrgang | 50 |
Ausgabenummer | 1 |
DOIs | |
Publikationsstatus | Veröffentlicht - Jan. 2022 |