Matthias Schymura: Complexity of linear relaxations in integer programming

Abstract: For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called its relaxation complexity rc(X). This parameter has been introduced by Kaibel & Weltge (2015) and captures the complexity of linear descriptions of X without using auxiliary variables.

Surprisingly, the following basic questions regarding rc(X) and its variant rc_Q(X), restricting the descriptions of X to rational polyhedra, are wide open in general:

(Q1) Do we always have rc(X) = rc_Q(X) ?

(Q2) Is rc(X) or rc_Q(X) algorithmically computable ?

(Q3) Do we always have rc(X) >= dim(X) + 1 ?

In the talk I describe how we use tools from combinatorics, geometry of numbers, and quantifier elimination to make progress on each of these questions. I focus on the occuring phenomena that separate small from large dimensions, and also such sets X whose convex hull contains interior integer points from those X that don't.

This is based on joint works with Gennadiy Averkov and Christopher Hojny.

Zoom link: https://kth-se.zoom.us/j/65455623260
Zoom meeting ID: 654 5562 3260