IDEAS home Printed from https://ideas.repec.org/p/hhb/aarbls/2006-008.html
   My bibliography  Save this paper

Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

Author

Listed:
  • Uchoa, Eduardo

    (Departamento de Engenharia de Producão)

  • Fukasawa, Ricardo

    (School of Industrial and Systems Engineering)

  • Lysgaard, Jens

    (Department of Accounting, Aarhus School of Business)

  • Pessoa, Artur

    (Departamento de Engenharia de Producão)

  • Poggi de Aragão, Marcus

    (Departamento de Informática)

  • Andrade, Diogo

    (RUTCOR)

Abstract

This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to q-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arbores- cence problem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. Moreover, a novel feature is introduced in such kind of algorithms. Powerful new cuts expressed over a very large set of variables could be added, without increasing the complexity of the pricing subproblem or the size of the LPs that are actually solved. Computational results on benchmark instances from the OR-Library show very signi¯cant improvements over previous algorithms. Several open instances could be solved to optimality

Suggested Citation

  • Uchoa, Eduardo & Fukasawa, Ricardo & Lysgaard, Jens & Pessoa, Artur & Poggi de Aragão, Marcus & Andrade, Diogo, 2006. "Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation," CORAL Working Papers L-2006-08, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    • Handle: RePEc:hhb:aarbls:2006-008
    as

    Download full text from publisher

    File URL: http://www.hha.dk/bs/wp/log/L_2006_08.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Daeki Kim & Cynthia Barnhart & Keith Ware & Gregory Reinhardt, 1999. "Multimodal Express Package Delivery: A Service Network Design Application," Transportation Science, INFORMS, vol. 33(4), pages 391-407, November.
    2. 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.
    3. Leslie Hall, 1996. "Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 219-234, August.
    4. Luis Gouveia, 1995. "A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem," Operations Research, INFORMS, vol. 43(1), pages 130-141, February.
    5. Leslie A. Hall & Thomas L. Magnanti, 1992. "A Polyhedral Intersection Theorem for Capacitated Spanning Trees," Mathematics of Operations Research, INFORMS, vol. 17(2), pages 398-410, May.
    6. L. Gouveia & P. Martins, 1999. "The Capacitated Minimal Spanning Tree Problem: An experiment with a hop‐indexedmodel," Annals of Operations Research, Springer, vol. 86(0), pages 271-294, January.
    7. Gouveia, Luis & Joao Lopes, Maria, 2005. "The capacitated minimum spanning tree problem: On improved multistar constraints," European Journal of Operational Research, Elsevier, vol. 160(1), pages 47-62, January.
    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. Kjeldsen, Karina Hjortshøj, 2008. "Classification of routing and scheduling problems in liner shipping," CORAL Working Papers L-2008-06, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    2. Lysgaard, Jens & Løber, Janni, 2008. "Scheduling participants of Assessment Centres," CORAL Working Papers L-2008-01, University of Aarhus, Aarhus School of Business, Department of Business Studies.

    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. Zhixing Luo & Hu Qin & T. C. E. Cheng & Qinghua Wu & Andrew Lim, 2021. "A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 452-476, May.
    2. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    3. Xiaojun Zhu & Shaojie Tang, 2021. "A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1446-1460, October.
    4. Cohn, Amy & Davey, Melinda & Schkade, Lisa & Siegel, Amanda & Wong, Caris, 2008. "Network design and flow problems with cross-arc costs," European Journal of Operational Research, Elsevier, vol. 189(3), pages 890-901, September.
    5. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    6. Scheibe, Kevin P. & Ragsdale, Cliff T., 2009. "A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem," European Journal of Operational Research, Elsevier, vol. 197(2), pages 773-784, September.
    7. Amberg, Anita & Domschke, Wolfgang & Vo[ss], Stefan, 2000. "Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees," European Journal of Operational Research, Elsevier, vol. 124(2), pages 360-376, July.
    8. Gouveia, Luis & Lopes, Maria Joao, 2000. "Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs," European Journal of Operational Research, Elsevier, vol. 121(2), pages 394-411, March.
    9. Li, Xiangyong & Wei, Kai & Guo, Zhaoxia & Wang, Wei & Aneja, Y.P., 2021. "An exact approach for the service network design problem with heterogeneous resource constraints," Omega, Elsevier, vol. 102(C).
    10. 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.
    11. Chu, James C., 2018. "Mixed-integer programming model and branch-and-price-and-cut algorithm for urban bus network design and timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 108(C), pages 188-216.
    12. Raymond A. Patterson & Erik Rolland, 2002. "Hybrid Fiber Coaxial Network Design," Operations Research, INFORMS, vol. 50(3), pages 538-551, June.
    13. Fernandes, Lucinda Matos & Gouveia, Luis, 1998. "Minimal spanning trees with a constraint on the number of leaves," European Journal of Operational Research, Elsevier, vol. 104(1), pages 250-261, January.
    14. C S Sung & S H Song, 2003. "Integrated service network design for a cross-docking supply chain network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(12), pages 1283-1295, December.
    15. Melchiori, Anna & Sgalambro, Antonino, 2020. "A branch and price algorithm to solve the Quickest Multicommodity k-splittable Flow Problem," European Journal of Operational Research, Elsevier, vol. 282(3), pages 846-857.
    16. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    17. Hall, Randolph W. & Lo, Shih-Che, 2002. "Truck Scheduling for Ground to Air Connectivity: Final Report," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt85v0x577, Institute of Transportation Studies, UC Berkeley.
    18. 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.
    19. Albert H. Schrotenboer & Evrim Ursavas & Iris F. A. Vis, 2019. "A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 53(4), pages 1001-1022, July.
    20. 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.

    More about this item

    Keywords

    No keywords;

    Statistics

    Access and download statistics

    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:hhb:aarbls:2006-008. 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: Helle Vinbaek Stenholt (email available below). General contact details of provider: https://edirc.repec.org/data/ifhhadk.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.