Refine
Year of publication
- 2009 (1)
Document Type
- ZIB-Report (1) (remove)
Language
- English (1) (remove)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1)
Keywords
- network detection (1) (remove)
Institute
Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.