The role of rationality in integer-programming relaxations

For a finite set $X \subset \Z^d$ that can be represented as $X = Q \cap \Z^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $\rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $\rc_\Q(X)$ restricts … Read more

Efficient MIP Techniques for Computing the Relaxation Complexity

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We … Read more

Computational Aspects of Relaxation Complexity: Possibilities and Limitation

The relaxation complexity $\mathrm{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 a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive … Read more