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

DOI10.1016/J.ORL.2021.11.009MaRDI QIDQ6366458arXivFDO

Authors Matthias Brugger, Andreas S. Schulz

Publication date 29 April 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2021.11.009

Mathematics Subject Classification ID

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

arXiv classification

cs.DMmath.COmath.OC

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.

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)