The <Emphasis Type="SmallCaps">Mcf</Emphasis>-separator: detecting and exploiting multi-commodity flow structures in MIPs

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.