On the Complexity of Recognizing Integrality and Total Dual Integrality of the {0,1/2}-Closure

Abstract The { 0 , 1 2 } -closure of a rational polyhedron { x : A x ≤ b } is obtained by adding all Gomory-Chvatal cuts that can be derived from the linear system A x ≤ b using multipliers in { 0 , 1 2 } . We show that deciding whether the { 0 , 1 2 } -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 { 0 , 1 2 } -closure derived from A x ≤ b is totally dual integral, is strongly NP-hard.