Open Collections

Description

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.