Decomposing Matrices into Blocks

Ralf Borndörfer  Carlos E. Ferreira  Alexander Martin
Konrad-Zuse-Zentrum Berlin University of São Paulo Konrad-Zuse-Zentrum Berlin
borndoerfer@zib.de  cef@ime.usp.br  martin@zib.de

In this talk we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called bordered block diagonal form. Given some matrix A, we try to assign as many rows as possible to some number β of blocks of 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 attack this matrix decomposition problem from a polyhedral point of view and develop a branchand-cut algorithm. We present several new classes of valid and facet-defining inequalities, discuss separation algorithms and the success of primal heuristics. Our computational results show that various matrices from the LP- and MIP-libraries Netlib and Miplib can indeed be decomposed into this form.