Structure Detection in Mixed-Integer Programs

Despite vast improvements in computational power, many large-scale optimization problems involving integer variables remain difficult to solve. Certain classes, however, can be efficiently solved by exploiting special structure. One such structure is the singly bordered block-diagonal (BBD) structure that lends itself to Dantzig-Wolfe decomposition, Lagrangian relaxation, and branch and price. We start by introducing a new measure of goodness to capture desired features in BBD structures such as granularity of the structure, homogeneity of the block sizes, and isomorphism of the blocks. We then use it to propose a new approach to identify the best BBD structure inherent in the constraint matrix. The main building block of the proposed approach is the use of a community detection methodology in lieu of graph/hypergraph partitioning methods to alleviate one major drawback of the existing approaches in the literature: predefining the number of blocks. When tested on MIPLIB2003/2010 instances and compared against the state-of-the-art technique, the proposed algorithm is found to identify very good structures and require shorter CPU time to reach comparable bounds, in most cases.