Packing, Covering and Partitioning Problems with Strongly Unimodular Constraint Matrices

A 0-1 matrix A is called strongly unimodular if all its nonsingular square submatrices are triangular. We present an efficient algorithm for linear programming problems in binary variables, when all constraints are of the packing, covering or partitioning type, and the constraint matrix is strongly unimodular. The algorithm uses a certain decomposition of strongly unimodular matrices into their so-called “restricted unimodular” components, and an efficient optimization algorithm for linear programs with restricted unimodular constraints.