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

DOI10.1016/J.ORL.2021.11.009arXiv2104.14486MaRDI QIDQ6366458FDOQ6366458

Matthias Brugger, Andreas S. Schulz

Publication date: 29 April 2021

Abstract: The $0,frac12$-closure of a rational polyhedron $xcolonAxleb$ is obtained by adding all Gomory-Chv'atal cuts that can be derived from the linear system $Axleb$ using multipliers in $0,frac12$. We show that deciding whether the $0,frac12$-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,frac12$-closure derived from $Axleb$ is totally dual integral, is strongly NP-hard.

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

This page was built for publication: On the Complexity of Recognizing Integrality and Total Dual Integrality of the $\{0,1/2\}$-Closure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366458)