文章基本信息

标题：The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs
其他标题：The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs
本地全文：下载
作者：Achterberg, Tobias ; Raack, Christian
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2010
页码：125-165
DOI：10.1007/mpc.v0i0.36
语种：English
出版社：Mathematical Programming Computation
摘要：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.
关键词：90C11; 90C35; 90-08