Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We are motivated by integer linear programs (ILPs) defined by constraint matrices with bounded determinants. Such matrices generalize the notion of totally-unimodular matrices. When the determinants are bounded by 2, the matrix is called bimodular. Artmann et al. give a polynomial-time algorithm for solving any ILP defined by a bimodular constraint matrix.

Complementing this result, Conforti et al. give a compact extended formulation for a particular class of bimodular-constrained ILPs, namely those that model the stable set polytope of a graph with odd cycle packing number 1. We demonstrate that their compact extended formulation can be modified to hold for polyhedra such that (1) the constraint matrix is bimodular, (2) the row-matroid generated by the constraint matrix is cographic and (3) the right-hand side is a linear combination of the columns of the constraint matrix. This generalizes the important special case from Conforti et al. concerning 4-connected graphs with odd cycle transversal number at least four.