A compact linear programming formulation of the maximum concurrent flow problem

We present an alternative linear programming formulation of the maximum concurrent flow problem (MCFP) termed the triples formulation. The standard formulations in the literature are the edge-path and node-edge formulations, which are known to be equivalent due to the Flow Decomposition Theorem. We present algorithms for deriving a triples solution from an edge-path solution and vice versa, and hence show that all three formulations are equivalent. Our new formulation leads to more compact linear programs than either the edge-path or node-path formulations. We show that the triples formulation often has half the number of rows and half the number of columns compared to the node-edge formulation. We report computational results comparing the solution times using the three formulations and the state-of-the-art linear programming solver CPLEX on a set of popular problem instances from the literature and a set of instances defined on random geometric graphs. The results indicate that the triples formulation can be solved more efficiently than the other two. We found that the CPLEX linear programming solvers solved 89% of the MCFP instances in our computational study faster with the triples formulation than it did with the other two formulations, typically two to four times faster than the node-edge formulation when available computer memory allowed both to be solved. The triples formulation appears to be particularly well suited for problem instances defined on dense graphs; on average, CPLEX solved these types of problems in our study 10 times faster with the triples formulation. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 68–87. 2015