OR Seminar - Samuel Fiorini

Samuel Fiorini (ULB)
Invited by Daniele Catanzaro

will give a presentation on :

Integer programs with nearly totally unimodular matrices: the cographic case

Abstract : 

It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Δ in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.
Our approach focuses on the case where A arises from M after removing k rows only, where k is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory.

First, we derive a strong proximity result for the case where A is a general totally unimodular matrix: Given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of [A I].

Second, for the case where A is transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph G. We observe that if G is 2-connected, then it has no rooted K_{2,t}-minor for t=Ω(kΔ). We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming.

This is joint work with Manuel Aprile (U Padova), Gwenaël Joret (ULB), Stefan Kober (ULB), Michał T. Seweryn (ULB / Charles U Prague), Stefan Weltge (TU Munich), Yelena Yuditsky (ULB).

  Samuel Fiorini