Premium
An extended model and a column generation algorithm for the planar multicommodity flow problem
Author(s) -
Alvelos Filipe,
de Carvalho J. M. Valério
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20161
Subject(s) - column generation , mathematics , solver , mathematical optimization , column (typography) , path (computing) , set (abstract data type) , flow (mathematics) , bundle , flow network , algorithm , computer science , connection (principal bundle) , materials science , geometry , composite material , programming language
We present a new model and a column generation algorithm for the linear minimum cost multicommodity flow problem. The new model has two differences when compared to the classic formulation based on flows on paths: it has an additional set of variables and an additional set of inequalities. The extra variables are associated with flows on circuits where some arcs are reversed. The extra inequalities assure that an optimal solution to the extended model can be converted to an optimal solution to the path formulation. In order to obtain an optimal solution to the extended model, we use column generation. The 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. Our present work is related to the use of dual–optimal inequalities in the sense that we extend a model with additional primal variables/dual inequalities. However, our extended model also has additional primal inequalities/dual variables. We present computational results of our method in planar instances and compare them 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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 3–16 2007