Parametrization of discrete optimization problems, subdeterminants and matrix-decomposition

The central goal of this talk is to identify parameters that explain the complexity of Integer linear programming defined as follows:

Let P be a polyhedron. Determine an integral point in P that maximizes a linear function.

It is obvious that the number of integer variables is such a parameter. However, in view of applications in very high dimensions, the question emerges whether we need to treat all variables as integers? In other words, can we reparametrize integer programs with significantly less integer variables?

A second much less obvious parameter associated with an integer linear program is the number Delta defined as the maximum absolute value of any square submatrix of a given integral matrix A with m rows and n columns. This leads us to the important open question whether we can solve integer linear programming in a polynomial running time in Delta and the instance size?

Regarding the first question, we exhibit a variety of examples that demonstrate how integer programs can be reformulated using much less integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determining the affine TU-dimension of a matrix.

Regarding the second question, we present several new results that illustrate why Delta is an important parameter about the complexity of integer linear programs associated with a given matrix A.

In particular, in the nondegenerate case integer linear programs with any constant value Delta can be solved in polynomial time. This extends earlier results of Veselov and Chirkov.