When: May 3, 2017, 12:30 PM
Location: 3rd Floor Orchard View Room , Discovery Building
Contact: 608-316-4401, email@example.com
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.
SILO is a lecture series with speakers from the UW faculty, graduate students or invited researchers that discuss mathematical related topics. The seminars are organized by WID’s Optimization research group and sponsored by generous support of the Advance Technology Group of the 3M Company and the Analytics Group of Northwestern Mutual.
SILO’s purpose is to provide a forum that helps connect and recruit mathematically-minded graduate students. SILO is a lunch-and-listen format, where speakers present interesting math topics while the audience eats lunch.