Decomposing Matrices into Blocks
Appeared in: SIAM J. on Opt. 9 (1998), Nr 1, 236-269
| SC 97-15 | Ralf Borndörfer, Carlos E. Ferreira, Alexander Martin
Decomposing Matrices into Blocks Appeared in: SIAM J. on Opt. 9 (1998), Nr 1, 236-269 | |
Original Version (MAR 1997)
Abstract: 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 
, we try to assign as
many rows as possible to some number of blocks of limited size such that no
two rows assigned 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 LP- and MIP-libraries NETLIB and MITLIB 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.