IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v54y2006i1p184-197.html
   My bibliography  Save this article

Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM

Author

Listed:
  • F. Babonneau

    (Logilab, HEC, Université de Genève, 40 Bd du Pont d’Arve, CH-1211 Geneva, Switzerland)

  • O. du Merle

    (Air France, Operations Research Department, 1 Avenue du Maréchal Devaux, 91550 Paray-Vieille-Poste, France)

  • J.-P. Vial

    (Logilab, HEC, Universitè de Genéve, 40 Bd du Pont d’Arve, CH-1211 Geneva, Switzerland)

Abstract

In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to be the case in many practical problems.

Suggested Citation

  • F. Babonneau & O. du Merle & J.-P. Vial, 2006. "Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM," Operations Research, INFORMS, vol. 54(1), pages 184-197, February.
    • Handle: RePEc:inm:oropre:v:54:y:2006:i:1:p:184-197
    DOI: 10.1287/opre.1050.0262
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1050.0262
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1050.0262?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. P. Chardaire & A. Lisser, 2002. "Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow Problems," Operations Research, INFORMS, vol. 50(2), pages 260-276, April.
    2. A. Ouorou & P. Mahey & J.-Ph. Vial, 2000. "A Survey of Algorithms for Convex Multicommodity Flow Problems," Management Science, INFORMS, vol. 46(1), pages 126-147, January.
    3. John W. Mamer & Richard D. McBride, 2000. "A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem," Management Science, INFORMS, vol. 46(5), pages 693-709, May.
    4. Judith M. Farvolden & Warren B. Powell & Irvin J. Lustig, 1993. "A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem," Operations Research, INFORMS, vol. 41(4), pages 669-693, August.
    5. Antonio Frangioni & Giorgio Gallo, 1999. "A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 370-393, November.
    6. J. L. Goffin & A. Haurie & J. P. Vial, 1992. "Decomposition and Nondifferentiable Optimization with the Projective Algorithm," Management Science, INFORMS, vol. 38(2), pages 284-302, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Frédéric Babonneau & Jean-Philippe Vial, 2008. "An Efficient Method to Compute Traffic Assignment Problems with Elastic Demands," Transportation Science, INFORMS, vol. 42(2), pages 249-260, May.
    2. Chu, Chih-Peng & Tsai, Jyh-Fa & Hu, Shou-Ren, 2012. "Optimal starting location of an HOV lane for a linear monocentric urban area," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(3), pages 457-466.
    3. Berit Dangaard Brouer & Christian Vad Karsten & David Pisinger, 2017. "Optimization in liner shipping," 4OR, Springer, vol. 15(1), pages 1-35, March.
    4. Berit Dangaard Brouer & Christian Vad Karsten & David Pisinger, 2018. "Optimization in liner shipping," Annals of Operations Research, Springer, vol. 271(1), pages 205-236, December.
    5. Bar-Gera, Hillel & Hellman, Fredrik & Patriksson, Michael, 2013. "Computational precision of traffic equilibria sensitivities in automatic network design and road pricing," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 485-500.
    6. Attila Bernáth & Tamás Király & Erika Kovács & Gergely Mádi-Nagy & Gyula Pap & Júlia Pap & Jácint Szabó & László Végh, 2013. "Algorithms for multiplayer multicommodity flow problems," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(4), pages 699-712, December.
    7. Bar-Gera, Hillel, 2010. "Traffic assignment by paired alternative segments," Transportation Research Part B: Methodological, Elsevier, vol. 44(8-9), pages 1022-1046, September.
    8. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    9. François Lamothe & Emmanuel Rachelson & Alain Haït & Cedric Baudoin & Jean-Baptiste Dupé, 2021. "Randomized rounding algorithms for large scale unsplittable flow problems," Journal of Heuristics, Springer, vol. 27(6), pages 1081-1110, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Frédéric Babonneau & Jean-Philippe Vial, 2008. "An Efficient Method to Compute Traffic Assignment Problems with Elastic Demands," Transportation Science, INFORMS, vol. 42(2), pages 249-260, May.
    2. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    3. Klose, Andreas & Gortz, Simon, 2007. "A branch-and-price algorithm for the capacitated facility location problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1109-1125, June.
    4. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    5. Kaj Holmberg & Di Yuan, 2003. "A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 15(1), pages 42-57, February.
    6. Claude Lemaréchal, 2007. "The omnipresence of Lagrange," Annals of Operations Research, Springer, vol. 153(1), pages 9-27, September.
    7. P. Chardaire & G. P. McKeown & S. A. Verity-Harrison & S. B. Richardson, 2005. "Solving a Time-Space Network Formulation for the Convoy Movement Problem," Operations Research, INFORMS, vol. 53(2), pages 219-230, April.
    8. P. Chardaire & A. Lisser, 2002. "Simplex and Interior Point Specialized Algorithms for Solving Nonoriented Multicommodity Flow Problems," Operations Research, INFORMS, vol. 50(2), pages 260-276, April.
    9. A. Ouorou & P. Mahey & J.-Ph. Vial, 2000. "A Survey of Algorithms for Convex Multicommodity Flow Problems," Management Science, INFORMS, vol. 46(1), pages 126-147, January.
    10. Andreas Klose & Andreas Drexl, 2005. "Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation," Management Science, INFORMS, vol. 51(11), pages 1689-1705, November.
    11. Zhang, M. & Pel, A.J., 2016. "Synchromodal hinterland freight transport: Model study for the port of Rotterdam," Journal of Transport Geography, Elsevier, vol. 52(C), pages 1-10.
    12. Gürel, Sinan, 2011. "A conic quadratic formulation for a class of convex congestion functions in network flow problems," European Journal of Operational Research, Elsevier, vol. 211(2), pages 252-262, June.
    13. Paraskevopoulos, Dimitris C. & Gürel, Sinan & Bektaş, Tolga, 2016. "The congested multicommodity network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 166-187.
    14. Hela Masri & Saoussen Krichen, 2018. "Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem," Annals of Operations Research, Springer, vol. 267(1), pages 353-377, August.
    15. Krzysztof C. Kiwiel & Torbjörn Larsson & P. O. Lindberg, 2007. "Lagrangian Relaxation via Ballstep Subgradient Methods," Mathematics of Operations Research, INFORMS, vol. 32(3), pages 669-686, August.
    16. Jeffery L. Kennington & Karen R. Lewis, 2004. "Generalized Networks: The Theory of Preprocessing and an Empirical Analysis," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 162-173, May.
    17. Paola Cappanera & Antonio Frangioni, 2003. "Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multicommodity Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 369-384, November.
    18. Samir Elhedhli & Jean-Louis Goffin, 2005. "Efficient Production-Distribution System Design," Management Science, INFORMS, vol. 51(7), pages 1151-1164, July.
    19. Morabito, Reinaldo & de Souza, Mauricio C. & Vazquez, Mariana, 2014. "Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks," European Journal of Operational Research, Elsevier, vol. 232(3), pages 618-629.
    20. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:54:y:2006:i:1:p:184-197. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.