Seminar: Christopher Hojny (TU/e)

Let X be the integer points contained in a polytope. The relaxation
complexity rc(X) 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
particular, it provides the minimum number of inequalities needed in any
integer programming formulation of X. Moreover, when restricting the
polyhedra P to be rational, rc_Q(X) denotes the corresponding rational
relaxation complexity of X.

In this presentation, I discuss several algorithmic aspects of finding
the relaxation complexity. First, a natural question is whether rc(X) is
actually computable. While this question is notoriously open in general,
I present an algorithm that finds rc(X) in dimension 2. Second, rc_Q(X)
is an upper bound on rc(X). A natural idea is thus to provide computable
lower bounds on rc(X) and computable upper bounds on rc_Q(X). If these
bounds match, rc(X) and rc_Q(X) have been found. I show that we can
indeed find a matching upper bound on rc_Q(X), whereas I discuss why
finding a matching lower bound for rc(X) seems to be more challenging.
Finally, the previously sketched idea only allows to compute rc(X) and
rc_Q(X) if both quantities coincide. I conclude this presentation by a
brief outline that rc(X) can be strictly smaller than rc_Q(X).

Video: