IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v29y2017i4p597-611.html
   My bibliography  Save this article

Exact Approaches for Designing Multifacility Buy-at-Bulk Networks

Author

Listed:
  • Ashwin Arulselvan

    (Department of Management Science, University of Strathclyde, Glasgow, Scotland G1 1XQ, United Kingdom)

  • Mohsen Rezapour

    (Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2R3, CanadaAuthor-Name: Wolfgang A. Welz
    Institute for Mathematics, Technical University of Berlin, Berlin 10623, Germany)

Abstract

We study a problem that integrates buy-at-bulk network design into the classical facility location problem. We consider a generalization of the facility location problem where multiple clients may share a capacitated network to connect to open facilities instead of requiring direct links. In this problem, we wish to open facilities, build a routing network by installing access cables of different costs and capacities, and route every client demand to an open facility. We provide a path-based formulation and we compare it with the natural compact formulation for this problem. We then design an exact branch-price-and-cut algorithm for solving the path-based formulation. We study the effect of two families of valid inequalities. In addition to this, we present three different types of primal heuristics and employ a hybrid approach to effectively combine these heuristics in order to improve the primal bounds. We finally report the results of our approach that were tested on a set of real world instances, as well as two sets of benchmark instances and evaluate the effects of our valid inequalities and primal heuristics.

Suggested Citation

  • Ashwin Arulselvan & Mohsen Rezapour, 2017. "Exact Approaches for Designing Multifacility Buy-at-Bulk Networks," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 597-611, November.
    • Handle: RePEc:inm:orijoc:v:29:y:2017:i:4:p:597-611
    DOI: 10.1287/ijoc.2017.0752
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2017.0752
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2017.0752?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. R. Ravi & Amitabh Sinha, 2006. "Approximation Algorithms for Problems Combining Facility Location and Network Design," Operations Research, INFORMS, vol. 54(1), pages 73-81, February.
    2. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    3. F. Sibel Salman & R. Ravi & John N. Hooker, 2008. "Solving the Capacitated Local Access Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 243-254, May.
    4. Álvarez-Miranda, Eduardo & Cacchiani, Valentina & Lodi, Andrea & Parriani, Tiziano & Schmidt, Daniel R., 2014. "Single-commodity robust network design problem: Complexity, instances and heuristic solutions," European Journal of Operational Research, Elsevier, vol. 238(3), pages 711-723.
    5. Cynthia Barnhart & Christopher A. Hane & Pamela H. Vance, 2000. "Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems," Operations Research, INFORMS, vol. 48(2), pages 318-326, April.
    Full references (including those not matched with items on IDEAS)

    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. Liang Chen & Wei-Kun Chen & Mu-Ming Yang & Yu-Hong Dai, 2021. "An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron," Journal of Global Optimization, Springer, vol. 81(3), pages 659-689, November.
    2. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    3. Seyed Hossein Hashemi Doulabi & Louis-Martin Rousseau & Gilles Pesant, 2016. "A Constraint-Programming-Based Branch-and-Price-and-Cut Approach for Operating Room Planning and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 432-448, August.
    4. Gamst, Mette & Neergaard Jensen, Peter & Pisinger, David & Plum, Christian, 2010. "Two- and three-index formulations of the minimum cost multicommodity k-splittable flow problem," European Journal of Operational Research, Elsevier, vol. 202(1), pages 82-89, April.
    5. Lienkamp, Benedikt & Schiffer, Maximilian, 2024. "Column generation for solving large scale multi-commodity flow problems for passenger transportation," European Journal of Operational Research, Elsevier, vol. 314(2), pages 703-717.
    6. 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.
    7. 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.
    8. Fortz, Bernard & Gouveia, Luís & Joyce-Moniz, Martim, 2017. "Models for the piecewise linear unsplittable multicommodity flow problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 30-42.
    9. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2017. "Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost," Transportation Science, INFORMS, vol. 51(2), pages 668-687, May.
    10. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    11. Yu Zhou & Leishan Zhou & Yun Wang & Xiaomeng Li & Zhuo Yang, 2017. "A practical model for the train-set utilization: The case of Beijing-Tianjin passenger dedicated line in China," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-24, May.
    12. Gamst, M. & Petersen, B., 2012. "Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem," European Journal of Operational Research, Elsevier, vol. 217(2), pages 278-286.
    13. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    14. Marie-Claude Côté & Bernard Gendron & Louis-Martin Rousseau, 2013. "Grammar-Based Column Generation for Personalized Multi-Activity Shift Scheduling," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 461-474, August.
    15. Chardy, M. & Costa, M.-C. & Faye, A. & Trampont, M., 2012. "Optimizing splitter and fiber location in a multilevel optical FTTH network," European Journal of Operational Research, Elsevier, vol. 222(3), pages 430-440.
    16. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    17. Ethem Çanakoğlu & İbrahim Muter & Tevfik Aytekin, 2021. "Integrating Individual and Aggregate Diversity in Top- N Recommendation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 300-318, January.
    18. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    19. Sankaran, Jayaram K., 1995. "Column generation applied to linear programs in course registration," European Journal of Operational Research, Elsevier, vol. 87(2), pages 328-342, December.
    20. Metrane, Abdelmoutalib & Soumis, François & Elhallaoui, Issmail, 2010. "Column generation decomposition with the degenerate constraints in the subproblem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 37-44, 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:inm:orijoc:v:29:y:2017:i:4:p:597-611. 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.