Article (Scientific journals)
Packing, covering and partitioning problems with strongly unimodular constraint matrices
Crama, Yves; Hammer, Peter L.; Ibaraki, Toshihide
1990In Mathematics of Operations Research, 15, p. 258-267
Peer Reviewed verified by ORBi
 

Files


Full Text
Packing covering SU matrices MOR 1990.pdf
Publisher postprint (510.66 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
packing; covering; partitioning; strong unimodularity; matrix decomposition
Abstract :
[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
Publication date :
1990
Journal title :
Mathematics of Operations Research
ISSN :
0364-765X
eISSN :
1526-5471
Publisher :
Institute for Operations Research (INFORMS)
Volume :
15
Pages :
258-267
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 24 December 2017

Statistics


Number of views
37 (2 by ULiège)
Number of downloads
0 (0 by ULiège)

OpenCitations
 
1

Bibliography


Similar publications



Contact ORBi