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

An algorithmic framework for the exact solution of tree-star problems

Author

Listed:
  • Leitner, Markus
  • Ljubić, Ivana
  • Salazar-González, Juan-José
  • Sinnl, Markus

Abstract

Many problems arising in the area of telecommunication ask for solutions with a tree-star topology. This paper proposes a general procedure for finding optimal solutions to a family of these problems. The family includes problems in the literature named as connected facility location, rent-or-buy and generalized Steiner tree-star. We propose a solution framework based on a branch-and-cut algorithm which also relies on sophisticated reduction and heuristic techniques. An important ingredient of this framework is a dual ascent procedure for asymmetric connected facility location. This paper shows how this procedure can be exploited in combination with various mixed integer programming formulations. Using the new framework, many benchmark instances in the literature for which only heuristic results were available so far, can be solved to provable optimality within seconds. To better assess the computational performance of the new approach, we additionally consider larger instances and provide optimal solutions for most of them too.

Suggested Citation

  • Leitner, Markus & Ljubić, Ivana & Salazar-González, Juan-José & Sinnl, Markus, 2017. "An algorithmic framework for the exact solution of tree-star problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 54-66.
    • Handle: RePEc:eee:ejores:v:261:y:2017:i:1:p:54-66
    DOI: 10.1016/j.ejor.2017.02.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717301170
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.02.011?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. Youngho Lee & Steve Y. Chiu & Jennifer Ryan, 1996. "A Branch and Cut Algorithm for a Steiner Tree-Star Problem," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 194-201, August.
    2. M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
    3. Chu, Chao-Hsien & Premkumar, G. & Chou, Hsinghua, 2000. "Digital data networks design using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 127(1), pages 140-158, November.
    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. Pereira, Armando Honorio & Mateus, Geraldo Robson & Urrutia, Sebastián Alberto, 2022. "Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks," European Journal of Operational Research, Elsevier, vol. 300(1), pages 207-220.
    2. Eduardo Álvarez-Miranda & Markus Sinnl, 2020. "A branch-and-cut algorithm for the maximum covering cycle problem," Annals of Operations Research, Springer, vol. 284(2), pages 487-499, January.
    3. Kuzbakov, Yerlan & Ljubić, Ivana, 2024. "New formulations for two location problems with interconnected facilities," European Journal of Operational Research, Elsevier, vol. 314(1), pages 51-65.

    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. M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
    2. Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
    3. Jian Sun & Haiyun Sheng & Yuefang Sun & Donglei Du & Xiaoyan Zhang, 2022. "Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2626-2641, November.
    4. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    5. Zhao Zhang & Jiao Zhou & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Computing Minimum k -Connected m -Fold Dominating Set in General Graphs," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 217-224, May.
    6. Stefan Gollowitzer & Bernard Gendron & Ivana Ljubić, 2013. "A cutting plane algorithm for the Capacitated Connected Facility Location Problem," Computational Optimization and Applications, Springer, vol. 55(3), pages 647-674, July.
    7. Altiparmak, Fulya & Dengiz, Berna, 2009. "A cross entropy approach to design of reliable networks," European Journal of Operational Research, Elsevier, vol. 199(2), pages 542-552, December.
    8. Chu, Chao-Hsien & Premkumar, G. & Chou, Hsinghua, 2000. "Digital data networks design using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 127(1), pages 140-158, November.
    9. Dong Liang & Wilbert E. Wilhelm, 2013. "Dual‐ascent and primal heuristics for production‐assembly‐distribution system design," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 1-18, February.
    10. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    11. Li, Gang & Balakrishnan, Anantaram, 2016. "Models and algorithms for network reduction," European Journal of Operational Research, Elsevier, vol. 248(3), pages 930-942.
    12. Jiao Zhou & Zhao Zhang & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Breaking the O (ln n ) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 225-235, May.
    13. Kuzbakov, Yerlan & Ljubić, Ivana, 2024. "New formulations for two location problems with interconnected facilities," European Journal of Operational Research, Elsevier, vol. 314(1), pages 51-65.
    14. John Gunnar Carlsson & Fan Jia, 2013. "Euclidean Hub-and-Spoke Networks," Operations Research, INFORMS, vol. 61(6), pages 1360-1382, December.
    15. 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.
    16. Steven Chamberland & Brunilde Sansò & Odile Marcotte, 2000. "Topological Design of Two-Level Telecommunication Networks with Modular Switches," Operations Research, INFORMS, vol. 48(5), pages 745-760, October.

    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:261:y:2017:i:1:p:54-66. 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.