Exact solution of multicommodity flow problems with branch-and-bound and column generation

We present a branch-and-price algorithm to solve the minimum cost multicommodity flow problem with general integer variables and multiple origins and destinations for each commodity. A path-based formulation is used. The linear relaxation is solved using column generation, doing the implicit pricing by solving shortest path problems (subproblem) with modified costs. Obtaining the optimal integer solution implies allowing columns to be generated in the nodes of the branch-and-bound tree. However, the branching constraints may destroy the structure of the subproblem. We develop a branching rule based on arcs flows that maintain the subproblem structure. The modified costs can now be negative, because of the branching constraints of type ‘greater-than-or-equal-to’, and the network of the subproblem may have negative cycles. Based on flow decomposition theorem we propose a procedure to deal with that issue efficiently. We present computational results for instances with different characteristics, such as number of nodes, number of commodities and density of the network. Also, we compare the results obtained by the branch-and-price algorithm with the results obtained by solving the arc formulation with CPLEX.