Structure Detection in Mixed-Integer Programs

Taghi Khaniyev (), Samir Elhedhli () and Fatih Safa Erenay ()
Additional contact information
Taghi Khaniyev: Department of Management Sciences, University of Waterloo, Waterloo, Ontario N2H 3G1, Canada
Samir Elhedhli: Department of Management Sciences, University of Waterloo, Waterloo, Ontario N2H 3G1, Canada
Fatih Safa Erenay: Department of Management Sciences, University of Waterloo, Waterloo, Ontario N2H 3G1, Canada

INFORMS Journal on Computing, 2018, vol. 30, issue 3, 570-587

Abstract: 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.

Keywords: structure detection; bordered block diagonal; community detection; goodness measure; Dantzig-Wolfe reformulation; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0797 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:30:y:2018:i:3:p:570-587

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().