IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v72y2018i3d10.1007_s10898-018-0661-y.html
   My bibliography  Save this article

The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation

Author

Listed:
  • Yixin Zhao

    (Nanjing University of Science and Technology)

  • Torbjörn Larsson

    (Linköping University)

  • Elina Rönnberg

    (Linköping University)

  • Panos M. Pardalos

    (University of Florida)

Abstract

A new and strong convexified formulation of the fixed charge transportation problem is provided. This formulation is obtained by integrating the concepts of Lagrangian decomposition and column generation. The decomposition is made by splitting the shipping variables into supply and demand side copies, while the columns correspond to extreme flow patterns for single sources or sinks. It is shown that the combination of Lagrangian decomposition and column generation provides a formulation whose strength dominates those of three other convexified formulations of the problem. Numerical results illustrate that our integrated approach has the ability to provide strong lower bounds. The Lagrangian decomposition yields a dual problem with an unbounded set of optimal solutions. We propose a regularized column generation scheme which prioritizes an optimal dual solution with a small $$l_1$$ l 1 -norm. We further demonstrate numerically that information gained from the strong formulation can also be used for constructing a small-sized core problem which yields high-quality upper bounds.

Suggested Citation

  • Yixin Zhao & Torbjörn Larsson & Elina Rönnberg & Panos M. Pardalos, 2018. "The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation," Journal of Global Optimization, Springer, vol. 72(3), pages 517-538, November.
    • Handle: RePEc:spr:jglopt:v:72:y:2018:i:3:d:10.1007_s10898-018-0661-y
    DOI: 10.1007/s10898-018-0661-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-018-0661-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-018-0661-y?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sun, Minghe & Aronson, Jay E. & McKeown, Patrick G. & Drinka, Dennis, 1998. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 441-456, April.
    2. Monique Guignard, 2003. "Lagrangean relaxation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 11(2), pages 151-200, December.
    3. Michel L. Balinski, 1961. "Fixed‐cost transportation problems," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 8(1), pages 41-54, March.
    4. John William Stroup, 1967. "Letter to the Editor—Allocation of Launch Vehicles to Space Missions: A Fixed-Cost Transportation Problem," Operations Research, INFORMS, vol. 15(6), pages 1157-1163, December.
    5. Jeff Kennington & Ed Unger, 1976. "A New Branch-and-Bound Algorithm for the Fixed-Charge Transportation Problem," Management Science, INFORMS, vol. 22(10), pages 1116-1126, June.
    6. Katta G. Murty, 1968. "Solving the Fixed Charge Problem by Ranking the Extreme Points," Operations Research, INFORMS, vol. 16(2), pages 268-279, April.
    7. Roberto Roberti & Enrico Bartolini & Aristide Mingozzi, 2015. "The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation," Management Science, INFORMS, vol. 61(6), pages 1275-1291, June.
    8. D. Klingman & A. Napier & J. Stutz, 1974. "NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, INFORMS, vol. 20(5), pages 814-821, January.
    9. R. E. Marsten & W. W. Hogan & J. W. Blankenship, 1975. "The B oxstep Method for Large-Scale Optimization," Operations Research, INFORMS, vol. 23(3), pages 389-405, June.
    10. L. Cooper & C. Drebes, 1967. "An approximate solution method for the fixed charge problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 14(1), pages 101-113.
    11. Gavin J. Bell & Bruce W. Lamar & Chris A. Wallace, 1999. "Capacity improvement, penalties, and the fixed charge transportation problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(4), pages 341-355, June.
    12. Hultberg, Tim H. & Cardoso, Domingos M., 1997. "The teacher assignment problem: A special case of the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 101(3), pages 463-473, September.
    13. L. Létocart & A. Nagih & N. Touati-Moungla, 2012. "Dantzig-Wolfe and Lagrangian decompositions in integer linear programming," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 4(3), pages 247-262.
    14. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    15. Richard S. Barr & Fred Glover & Darwin Klingman, 1981. "A New Optimization Method for Large Scale Fixed Charge Transportation Problems," Operations Research, INFORMS, vol. 29(3), pages 448-463, June.
    16. Larsson, Torbjörn & Patriksson, Michael & Rydergren, Clas, 2004. "A column generation procedure for the side constrained traffic equilibrium problem," Transportation Research Part B: Methodological, Elsevier, vol. 38(1), pages 17-38, January.
    17. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    18. Wright, Don D. & von Lanzenauer, Christoph Haehling, 1989. "Solving the fixed charge problem with Lagrangian relaxation and cost allocation heuristics," European Journal of Operational Research, Elsevier, vol. 42(3), pages 305-312, October.
    19. P. Manimaran & V. Selladurai & Rajesh Ranganathan & G. Sasikumar, 2011. "Genetic Algorithm for optimisation of distribution system in a single stage supply chain network with fixed charges," International Journal of Industrial and Systems Engineering, Inderscience Enterprises Ltd, vol. 7(3), pages 292-316.
    20. Paul Gray, 1971. "Technical Note—Exact Solution of the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 19(6), pages 1529-1538, October.
    21. Patrick McKeown, 1975. "Technical Note—A Vertex Ranking Procedure for Solving the Linear Fixed-Charge Problem," Operations Research, INFORMS, vol. 23(6), pages 1183-1191, December.
    22. Larsson, Torbjorn & Migdalas, Athanasios & Ronnqvist, Mikael, 1994. "A Lagrangean heuristic for the capacitated concave minimum cost network flow problem," European Journal of Operational Research, Elsevier, vol. 78(1), pages 116-129, October.
    23. Jesús Sáez Aguado, 2009. "Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems," Annals of Operations Research, Springer, vol. 172(1), pages 45-69, November.
    24. Erika Buson & Roberto Roberti & Paolo Toth, 2014. "A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 62(5), pages 1095-1106, October.
    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. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).

    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. Erika Buson & Roberto Roberti & Paolo Toth, 2014. "A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation Problem," Operations Research, INFORMS, vol. 62(5), pages 1095-1106, October.
    2. Jesús Sáez Aguado, 2009. "Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems," Annals of Operations Research, Springer, vol. 172(1), pages 45-69, November.
    3. Roberto Roberti & Enrico Bartolini & Aristide Mingozzi, 2015. "The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation," Management Science, INFORMS, vol. 61(6), pages 1275-1291, June.
    4. Jeffery L. Kennington & Charles D. Nicholson, 2010. "The Uncapacitated Time-Space Fixed-Charge Network Flow Problem: An Empirical Investigation of Procedures for Arc Capacity Assignment," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 326-337, May.
    5. Sun, Minghe & Aronson, Jay E. & McKeown, Patrick G. & Drinka, Dennis, 1998. "A tabu search heuristic procedure for the fixed charge transportation problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 441-456, April.
    6. Gurwinder Singh & Amarinder Singh, 2021. "Solving fixed-charge transportation problem using a modified particle swarm optimization algorithm," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 12(6), pages 1073-1086, December.
    7. Klose, Andreas & Drexl, Andreas, 2001. "Combinatorial optimisation problems of the assignment type and a partitioning approach," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 545, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Alexey Sorokin & Vladimir Boginski & Artyom Nahapetyan & Panos M. Pardalos, 2013. "Computational risk management techniques for fixed charge network flow problems with uncertain arc failures," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 99-122, January.
    9. A. N. Balaji & J. Mukund Nilakantan & Izabela Nielsen & N. Jawahar & S. G. Ponnambalam, 2019. "Solving fixed charge transportation problem with truck load constraint using metaheuristics," Annals of Operations Research, Springer, vol. 273(1), pages 207-236, February.
    10. Lev, Benjamin & Kowalski, Krzysztof, 2011. "Modeling fixed-charge problems with polynomials," Omega, Elsevier, vol. 39(6), pages 725-728, December.
    11. Jawahar, N. & Balaji, A.N., 2009. "A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge," European Journal of Operational Research, Elsevier, vol. 194(2), pages 496-537, April.
    12. Adlakha, Veena & Kowalski, Krzysztof & Wang, Simi & Lev, Benjamin & Shen, Wenjing, 2014. "On approximation of the fixed charge transportation problem," Omega, Elsevier, vol. 43(C), pages 64-70.
    13. Kowalski, Krzysztof & Lev, Benjamin & Shen, Wenjing & Tu, Yan, 2014. "A fast and simple branching algorithm for solving small scale fixed-charge transportation problem," Operations Research Perspectives, Elsevier, vol. 1(1), pages 1-5.
    14. Bertazzi, Luca & Maggioni, Francesca, 2018. "A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach," European Journal of Operational Research, Elsevier, vol. 267(2), pages 555-569.
    15. Bala Shetty, 1990. "A relaxation/decomposition algorithm for the fixed charged network problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 37(2), pages 327-340, April.
    16. Gen, Mitsuo & Kumar, Anup & Ryul Kim, Jong, 2005. "Recent network design techniques using evolutionary algorithms," International Journal of Production Economics, Elsevier, vol. 98(2), pages 251-261, November.
    17. Dimitri J. Papageorgiou & Alejandro Toriello & George L. Nemhauser & Martin W. P. Savelsbergh, 2012. "Fixed-Charge Transportation with Product Blending," Transportation Science, INFORMS, vol. 46(2), pages 281-295, May.
    18. Aristide Mingozzi & Roberto Roberti, 2018. "An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns," Transportation Science, INFORMS, vol. 52(2), pages 229-238, March.
    19. V. Adlakha & K. Kowalski, 2015. "Fractional Polynomial Bounds for the Fixed Charge Problem," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 1026-1038, March.
    20. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.

    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:spr:jglopt:v:72:y:2018:i:3:d:10.1007_s10898-018-0661-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.