Open Collections

Bimodular Integer Linear Programming and Beyond

Banff International Research Station for Mathematical Innovation and Discovery

In this talk, I will show how any integer linear program (ILP) defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2} can be solved efficiently; even in strongly polynomial time. This is a natural extension of the well-known fact that ILPs with totally unimodular (TU) constraint matrices are polynomial-time solvable, which readily follows by the natural integrality of polytopes defined by a TU constraint matrix and integral right-hand sides. To derive this result we combine several techniques. In particular, the problem is first reduced to a particular parity-constrained ILP over a TU constraint matrix. We then leverage Seymour's decomposition of TU matrices to break this parity-constrained ILP into simpler base problems. Finally, we show how these base problems can be solved efficiently by combinatorial optimization techniques, including parity-constrained submodular minimization, and how to derive an optimal solution to the initial ILP from optimal solutions to base problems. Moreover, I will highlight some of the many open problems in this field and discuss recent results related to possible extensions to larger subdeterminants.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: ETH Zurich

2018-05-13

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65828

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/