Decomposing Matrices into Blocks

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 $\beta$ of blocks of size $\kappa$ 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 branch-and-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 will show that various matrices from the LP- amd
MIP-libraries Netlib and Miplib can indeed be decomposed into bordered
block diagonal form.