Optimization Online


The Mcf-Separator Detecting and Exploiting Multi-Commodity Flow Structures in MIPs

Tobias Achterberg(achterberg***at***de.ibm.com)
Christian Raack(raack***at***zib.de)

Abstract: 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 (c-MIR) 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.

Keywords: mixed integer programming, network detection, cut-based inequalities, separator, Cplex, Scip

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Network Optimization

Citation: ZIB Report ZR-09-38, November 2009, Zuse Institute Berlin, Takustr. 7, 14195 Berlin

Download: [Postscript][PDF]

Entry Submitted: 11/28/2009
Entry Accepted: 11/28/2009
Entry Last Modified: 11/28/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society