[en] 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 cosntraints.
Disciplines :
Mathematics
Author, co-author :
Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Hammer, Peter L.
Ibaraki, Toshihide
Language :
English
Title :
Packing, covering and partitioning problems with strongly unimodular constraint matrices
