Christopher Hojny - The role of rationality in integer programming relaxations

Christopher Hojny - Eindhoven University of Technology

The role of rationality in integer programming relaxations

Abstract: Integer programming is a powerful tool for solving optimization problems, for instance, in the field of combinatorial optimization. To be able to solve an optimization problem by means of integer programming, two ingredients are necessary: (i) a suitable encoding X of the problem's feasible solutions and (ii) a system of linear inequalities that separates the integer points in X from the remaining integer points. Any such system of linear inequalities is called a relaxation of X. The focus in (ii) was mostly on identifying facet-defining inequalities of the convex hull of X. Such inequality systems, however, are typically exponentially large and one may wonder about the minimum number of inequalities in any relaxation of X. This quantity is called the relaxation complexity of X. The minimum number of inequalities of a relaxation with rational coefficients is called the rational relaxation complexity.

In this presentation, I will discuss the impact of rationality on the relaxation complexity. I will focus on the the vertex set Y(d) of the standard simplex in dimension d, which consists of the d canonical unit vectors and the null vector. While every rational relaxation of Y(d) needs at least d+1 inequalities, I will show that Y(d) admits a relaxation with at most d inequalities if d is at least 5. That is, irrationality can reduce the minimal size of a relaxation, which answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, Mathematical Programming, 154(1):407–425, 2015). In the main part of this presentation, I will show that the relaxation complexity of Y(d) grows sublinearly. That is, the gap between the relaxation complexity and rational relaxation complexity can be arbitrarily large.

This is joint work with Manuel Aprile, Gennadiy Averkov, and Marco Di Summa.

Bio: Christopher Hojny is an assistant professor working at TU/e since October 2019. His main research topic is the development of efficient techniques to handle symmetries in mixed-integer programs. Besides symmetry handling, he is also interested in theoretical properties of integer programs (e.g., the existence of formulations with certain properties) and developing integer programming approaches to solve combinatorial optimization problems. Christopher is also a co-developer of the academic solver SCIP.