Using Circuit Variables to Accelerate Column Generation in Planar Multicommodity Flows

In this work we present a way of accelerating a column generation algorithm for the linear minimum cost multicommodity flow problem. We use a new model that, besides the usual variables corresponding to flows on paths, has a polynomial number of extra variables, corresponding to flows on circuits. Those extra variables are explicitly considered in the restricted master problem, from the beginning of the column generation process. The subproblem remains a set of shortest path problems, one for each commodity. We present computational results for the comparison of this new approach with standard column generation, a bundle method and a general-purpose solver. For the tested instances, there is an effective improvement in computational time of the column generation method when the extended model is used