Abstract
We show that any integer linear program (ILP) that is bimodular, which includes ILPs 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 strongly polynomial-time solvable.
To derive our result we combine several techniques. In particular, starting from an optimal vertex solution v to the natural linear relaxation, we show how v can be rounded in several steps through combinatorial techniques to an optimal integral solution. More precisely, we first reduce the rounding problem 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, which can be rephrased as combinatorial optimization problems and solved with combinatorial techniques, including parity-constrained submodular minimization. Finally, we show how efficient procedures for the base problems can be propagated up through Seymour's TU decomposition to round v to an optimal integral solution.