A strongly polynomial algorithm for bimodular integer linear programming

We present a strongly polynomial algorithm to solve integer programs of the form max{ c T x : Ax ≤ b , x εℤ n }, for A εℤ m X n with rank ( A )= n , b ε≤ m , c ε≤ n , and where all determinants of ( n X n )-sub-matrices of A are bounded by 2 in absolute value. In particular, this implies that integer programs max{ c T x : Q x ≤ b , x εℤ ≥0 n }, where Q ε ℤ m X n has the property that all subdeterminants are bounded by 2 in absolute value, can be solved in strongly polynomial time. We thus obtain an extension of the well-known result that integer programs with constraint matrices that are totally unimodular are solvable in strongly polynomial time.

Authors

• Stephan Artmann
• Robert Weismantel
• Rico Zenklusen

Keywords

• Integer programming
• bounded subdeterminants
• combinatorial optimization
• total unimodularity