Matthias Schymura: Complexity of linear relaxations in integer programming
Time: Wed 2021-03-31 10.15 - 11.15
Location: Zoom meeting ID: 654 5562 3260
Participating: Matthias Schymura (BTU Cottbus-Senftenberg)
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