TY - GEN
T1 - Computational Aspects of Relaxation Complexity
AU - Averkov, Gennadiy
AU - Hojny, Christopher
AU - Schymura, Matthias
PY - 2021
Y1 - 2021
N2 - The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rcQ(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. We also present an explicit formula for rc(X) of a specific class of sets X and present numerical experiments on the distribution of rc(X) in dimension 2.
AB - The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is an important tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rcQ(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dimensional. We also present an explicit formula for rc(X) of a specific class of sets X and present numerical experiments on the distribution of rc(X) in dimension 2.
KW - Integer programming formulation
KW - Relaxation complexity
UR - http://www.scopus.com/inward/record.url?scp=85106151173&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-73879-2_26
DO - 10.1007/978-3-030-73879-2_26
M3 - Conference contribution
SN - 9783030738785
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 368
EP - 382
BT - Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings
A2 - Singh, Mohit
A2 - Williamson, David P.
ER -