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

A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem

Author

Listed:
  • Richard Freling

    (Formerly with Econometric Institute, Erasmus University Rotterdam, Rotterdam, The Netherlands, and ORTEC Consultants B.V., Gouda, The Netherlands)

  • H. Edwin Romeijn

    (Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611-6595)

  • Dolores Romero Morales

    (Saïd Business School, University of Oxford, Oxford OX 1HP, United Kingdom)

  • Albert P. M. Wagelmans

    (Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands)

Abstract

In this paper, we propose a multiperiod single-sourcing problem (MPSSP), which takes both transportation and inventory into consideration, suitable for evaluating the performance of a logistics distribution network in a dynamic environment. We reformulate the MPSSP as a Generalized Assignment Problem (GAP) with a convex objective function. We then extend a branch-and-price algorithm that was developed for the GAP to this problem. The pricing problem is a so-called Penalized Knapsack Problem (PKP), which is a knapsack problem where the objective function includes an additional convex term penalizing the total use of capacity of the knapsack. The optimal solution of the relaxation of the integrality constraints in the PKP shows a similar structure to the optimal solution of the knapsack problem, that allows for an efficient solution procedure for the pricing problem. We perform an extensive numerical study of the branch-and-price algorithm.

Suggested Citation

  • Richard Freling & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2003. "A Branch-and-Price Algorithm for the Multiperiod Single-Sourcing Problem," Operations Research, INFORMS, vol. 51(6), pages 922-939, December.
    • Handle: RePEc:inm:oropre:v:51:y:2003:i:6:p:922-939
    DOI: 10.1287/opre.51.6.922.24914
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.51.6.922.24914
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.51.6.922.24914?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. H. Edwin Romeijn & Dolores Romero Morales, 2003. "An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(5), pages 412-437, August.
    2. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    3. Cattrysse, Dirk G. & Van Wassenhove, Luk N., 1992. "A survey of algorithms for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 60(3), pages 260-272, August.
    4. H. Edwin Romeijn & Nanda Piersma, 2000. "A Probabilistic Feasibility and Value Analysis of the Generalized Assignment Problem," Journal of Combinatorial Optimization, Springer, vol. 4(3), pages 325-355, September.
    5. Fleischmann, Bernhard, 1993. "Designing distribution systems with transport economies of scale," European Journal of Operational Research, Elsevier, vol. 70(1), pages 31-42, October.
    6. Duran, F., 1987. "A large mixed integer production and distribution program," European Journal of Operational Research, Elsevier, vol. 28(2), pages 207-217, February.
    7. Martin Savelsbergh, 1997. "A Branch-and-Price Algorithm for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 45(6), pages 831-841, December.
    8. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    9. H. Edwin Romeijn & Dolores Romero Morales, 2001. "Generating Experimental Data for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 49(6), pages 866-878, December.
    10. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    11. Cattrysse, Dirk. G. & Salomon, Marc & Van Wassenhove, Luk N., 1994. "A set partitioning heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 72(1), pages 167-174, January.
    12. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    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. Malaguti, Enrico & Monaci, Michele & Paronuzzi, Paolo & Pferschy, Ulrich, 2019. "Integer optimization with penalized fractional values: The Knapsack case," European Journal of Operational Research, Elsevier, vol. 273(3), pages 874-888.
    2. Gebennini, Elisa & Gamberini, Rita & Manzini, Riccardo, 2009. "An integrated production-distribution model for the dynamic location and allocation problem with safety stock optimization," International Journal of Production Economics, Elsevier, vol. 122(1), pages 286-304, November.
    3. Wei Huang & H. Edwin Romeijn & Joseph Geunes, 2005. "The continuous‐time single‐sourcing problem with capacity expansion opportunities," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 193-211, April.
    4. Dinçer Konur & Joseph Geunes, 2019. "Integrated districting, fleet composition, and inventory planning for a multi-retailer distribution system," Annals of Operations Research, Springer, vol. 273(1), pages 527-559, February.
    5. Tancrez, Jean-Sébastien & Lange, Jean-Charles & Semal, Pierre, 2012. "A location-inventory model for large three-level supply chains," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(2), pages 485-502.
    6. Zhalechian, M. & Tavakkoli-Moghaddam, R. & Zahiri, B. & Mohammadi, M., 2016. "Sustainable design of a closed-loop location-routing-inventory supply chain network under mixed uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 182-214.
    7. Jia Shu, 2010. "An Efficient Greedy Heuristic for Warehouse-Retailer Network Design Optimization," Transportation Science, INFORMS, vol. 44(2), pages 183-192, May.
    8. Emilio Carrizosa & Vanesa Guerrero & Dolores Romero Morales, 2023. "On mathematical optimization for clustering categories in contingency tables," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(2), pages 407-429, June.

    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. Richard Freling & H. Edwin Romeijn & Dolores Romero Morales & Albert P.M. Wagelmans, 1999. "A Branch and Price Algorithm for the Multi-Period Single-Sourcing Problem," Tinbergen Institute Discussion Papers 99-092/4, Tinbergen Institute.
    2. H. Edwin Romeijn & Dolores Romero Morales, 2003. "An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(5), pages 412-437, August.
    3. H. Edwin Romeijn & Dolores Romero Morales, 2001. "Generating Experimental Data for the Generalized Assignment Problem," Operations Research, INFORMS, vol. 49(6), pages 866-878, December.
    4. Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    5. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    6. 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.
    7. Ravindra K. Ahuja & Wei Huang & H. Edwin Romeijn & Dolores Romero Morales, 2007. "A Heuristic Approach to the Multi-Period Single-Sourcing Problem with Production and Inventory Capacities and Perishability Constraints," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 14-26, February.
    8. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    9. Amy Cohn & Michael Magazine & George Polak, 2009. "Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(3), pages 215-225, April.
    10. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    11. Huisman, D. & Jans, R.F. & Peeters, M. & Wagelmans, A.P.M., 2003. "Combining Column Generation and Lagrangian Relaxation," ERIM Report Series Research in Management ERS-2003-092-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    12. Romeijn, H.E. & Romero Morales, D., 2000. "A Greedy Heuristic for a Three-Level Multi-Period Single-Sourcing Problem," ERIM Report Series Research in Management ERS-2000-04-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    13. Diaz, Juan A. & Fernandez, Elena, 2001. "A Tabu search heuristic for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 132(1), pages 22-38, July.
    14. Thomas C. Sharkey & Joseph Geunes & H. Edwin Romeijn & Zuo‐Jun Max Shen, 2011. "Exact algorithms for integrated facility location and production planning problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(5), pages 419-436, August.
    15. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    16. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    17. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    18. Robert M. Nauss, 2003. "Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 249-266, August.
    19. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    20. Valerio de Carvalho, J. M., 2002. "LP models for bin packing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 253-273, September.

    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:51:y:2003:i:6:p:922-939. 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.