Speaker: Christopher Hojny (TU/e)
Title: Relaxation Complexity: Algorithmic Possibilities and Limitations
Abstract:
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).
