Decomposing Matrices into Blocks

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: Borndörfer R, E. Ferreira C, Martin A
Zeitschrift: SIAM Journal on Optimization
Verlag: Society for Industrial and Applied Mathematics
Jahr der Veröffentlichung: 1998
Band: 9
Seitenbereich: 236 -- 269
ISSN: 1052-6234
Sprache: Englisch


In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called bordered block diagonal form. More precisely, given some matrix A, we try to assign as many rows as possible to some number β of blocks of size script K such that no two rows as signed to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the linear programming and mixed integer programming libraries Netlib and Miplib can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)
University of São Paulo / Universidade de São Paulo (USP)


Borndörfer, R., E. Ferreira, C., & Martin, A. (1998). Decomposing Matrices into Blocks. SIAM Journal on Optimization, 9, 236 -- 269.

Borndörfer, Ralf, Carlos E. Ferreira, and Alexander Martin. "Decomposing Matrices into Blocks." SIAM Journal on Optimization 9 (1998): 236 -- 269.


Zuletzt aktualisiert 2018-07-08 um 21:41