Mathematical Programming Computation, Volume 2, Number 2 / June 2010

Font Size:  Small  Medium  Large

The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs

Tobias Achterberg, Christian Raack

Abstract


Given a general mixed integer program, 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 but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of mixed integer programs coming from network design problems by a factor two on average.We show that almost 10% of the instances in general testsets contain consistent embedded networks. For these instances the computation time is decreased by 18% on average.

Full Text: PDF

mpc footer
© MPS 2008-2019