IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v212y2011i2p263-276.html
   My bibliography  Save this article

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Author

Listed:
  • Akgün, Ibrahim
  • Tansel, Barbaros Ç.

Abstract

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).

Suggested Citation

  • Akgün, Ibrahim & Tansel, Barbaros Ç., 2011. "New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints," European Journal of Operational Research, Elsevier, vol. 212(2), pages 263-276, July.
    • Handle: RePEc:eee:ejores:v:212:y:2011:i:2:p:263-276
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(11)00105-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Gouveia, Luis, 1996. "Multicommodity flow models for spanning trees with hop constraints," European Journal of Operational Research, Elsevier, vol. 95(1), pages 178-190, November.
    2. Hanif D. Sherali & Patrick J. Driscoll, 2002. "On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems," Operations Research, INFORMS, vol. 50(4), pages 656-669, August.
    3. Gouveia, Luis & Pires, Jose Manuel, 1999. "The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints," European Journal of Operational Research, Elsevier, vol. 112(1), pages 134-146, January.
    4. Luis Gouveia, 1998. "Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 180-188, May.
    5. Pirkul, Hasan & Soni, Samit, 2003. "New formulations and solution procedures for the hop constrained network design problem," European Journal of Operational Research, Elsevier, vol. 148(1), pages 126-140, July.
    6. Larry J. LeBlanc & Jerome Chifflet & Philippe Mahey, 1999. "Packet Routing in Telecommunication Networks with Path and Flow Restrictions," INFORMS Journal on Computing, INFORMS, vol. 11(2), pages 188-197, May.
    7. Anantaram Balakrishnan & Kemal Altinkemer, 1992. "Using a Hop-Constrained Model to Generate Alternative Communication Network Design," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 192-205, May.
    8. Gouveia, Luis & Requejo, Cristina, 2001. "A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 539-552, August.
    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. Francesco Carrabs & Raffaele Cerulli & Manlio Gaudioso & Monica Gentili, 2013. "Lower and upper bounds for the spanning tree with minimum branch vertices," Computational Optimization and Applications, Springer, vol. 56(2), pages 405-438, October.
    2. Iago A. Carvalho & Marco A. Ribeiro, 2020. "An exact approach for the Minimum-Cost Bounded-Error Calibration Tree problem," Annals of Operations Research, Springer, vol. 287(1), pages 109-126, April.

    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. Costa, Alysson M. & Cordeau, Jean-François & Laporte, Gilbert, 2008. "Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints," European Journal of Operational Research, Elsevier, vol. 190(1), pages 68-78, October.
    2. 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.
    3. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    4. Iago A. Carvalho & Amadeu A. Coco, 2023. "On solving bi-objective constrained minimum spanning tree problems," Journal of Global Optimization, Springer, vol. 87(1), pages 301-323, September.
    5. De Boeck, Jérôme & Fortz, Bernard, 2018. "Extended formulation for hop constrained distribution network configuration problems," European Journal of Operational Research, Elsevier, vol. 265(2), pages 488-502.
    6. Quentin Botton & Bernard Fortz & Luis Gouveia & Michael Poss, 2013. "Benders Decomposition for the Hop-Constrained Survivable Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 13-26, February.
    7. BOTTON, Quentin & FORTZ, Bernard & GOUVEIA, Luis & POSS, Michael, 2011. "Benders decomposition for the hop-constrained survivable network design problem," LIDAM Discussion Papers CORE 2011037, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Jose Manuel García, 2024. "New strategy for anti-loop formulations," OPSEARCH, Springer;Operational Research Society of India, vol. 61(4), pages 2346-2359, December.
    9. Gouveia, Luis & Janssen, Eric, 1998. "Designing reliable tree networks with two cable technologies," European Journal of Operational Research, Elsevier, vol. 105(3), pages 552-568, March.
    10. Paola Cappanera & Maria Grazia Scutellà, 2011. "Color-Coding Algorithms to the Balanced Path Problem: Computational Issues," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 446-459, August.
    11. Balma, Ali & Salem, Safa Ben & Mrad, Mehdi & Ladhari, Talel, 2018. "Strong multi-commodity flow formulations for the asymmetric traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 271(1), pages 72-79.
    12. Pirkul, Hasan & Soni, Samit, 2003. "New formulations and solution procedures for the hop constrained network design problem," European Journal of Operational Research, Elsevier, vol. 148(1), pages 126-140, July.
    13. Khachai, Daniil & Sadykov, Ruslan & Battaia, Olga & Khachay, Michael, 2023. "Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm," European Journal of Operational Research, Elsevier, vol. 309(2), pages 488-505.
    14. Okan Arslan & Ola Jabali & Gilbert Laporte, 2020. "A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 120-134, January.
    15. Gouveia, Luis & Requejo, Cristina, 2001. "A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 539-552, August.
    16. Ivana Ljubić & Stefan Gollowitzer, 2013. "Layered Graph Approaches to the Hop Constrained Connected Facility Location Problem," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 256-270, May.
    17. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    18. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    19. Grigory Pastukhov & Alexander Veremyev & Vladimir Boginski & Eduardo L. Pasiliao, 2014. "Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 462-486, April.
    20. Luís Gouveia & Pedro Patrício & Amaro Sousa, 2008. "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM," Networks and Spatial Economics, Springer, vol. 8(1), pages 3-21, March.

    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:eee:ejores:v:212:y:2011:i:2:p:263-276. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.