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 -