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

Solving the Two-Connected Network with Bounded Meshes Problem

Author

Listed:
  • Bernard Fortz

    (Institut de Statistique et de Recherche Opérationnelle, SMG, Université Libre de Bruxelles, Belgium)

  • Martine Labbé

    (Institut de Statistique et de Recherche Opérationnelle, SMG, Université Libre de Bruxelles, Belgium)

  • Francesco Maffioli

    (DEI, Politecnico di Milano, Italy)

Abstract

We study the problem of designing at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “mesh”) does not exceed a given length K . This problem arises in the design of fiber-optic-based backbone telecommunication networks. A Branch-and-Cut approach to this problem is presented for which we introduce several families of valid inequalities and discuss the corresponding separation algorithms. Because the size of the problems solvable to optimality by this approach is too small, we also develop some heuristics. The computational performances of these exact and approximate methods are then thoroughly assessed both on randomly generated instances as well as instances suggested by real applications.

Suggested Citation

  • Bernard Fortz & Martine Labbé & Francesco Maffioli, 2000. "Solving the Two-Connected Network with Bounded Meshes Problem," Operations Research, INFORMS, vol. 48(6), pages 866-877, December.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:6:p:866-877
    DOI: 10.1287/opre.48.6.866.12390
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.6.866.12390
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.6.866.12390?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. Martin Grötschel & Clyde L. Monma & Mechthild Stoer, 1992. "Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints," Operations Research, INFORMS, vol. 40(2), pages 309-330, April.
    2. Dimitris Alevras & Martin Grötschel & Roland Wessäly, 1998. "Cost-efficient network synthesis from leased lines," Annals of Operations Research, Springer, vol. 76(0), pages 1-20, January.
    3. BIENSTOCK, Daniel & CHOPRA, Sunil & GÜNLÜK, Oktay & TSAI, Chih-Yang, 1998. "Minimum cost capacity installation for multicommodity network flows," LIDAM Reprints CORE 1391, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Clyde L. Monma & David F. Shallcross, 1989. "Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints," Operations Research, INFORMS, vol. 37(4), pages 531-541, 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. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "The Profitable Arc Tour Problem: Solution with a Branch-and-Price Algorithm," Transportation Science, INFORMS, vol. 39(4), pages 539-552, November.
    2. Alessandro Hill & Stefan Voß, 2016. "Optimal capacitated ring trees," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(2), pages 137-166, May.

    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. Yogesh Agarwal, 2013. "Design of Survivable Networks Using Three- and Four-Partition Facets," Operations Research, INFORMS, vol. 61(1), pages 199-213, February.
    2. Yogesh K. Agarwal, 2002. "Design of Capacitated Multicommodity Networks with Multiple Facilities," Operations Research, INFORMS, vol. 50(2), pages 333-344, April.
    3. Ellis L. Johnson & George L. Nemhauser & Martin W.P. Savelsbergh, 2000. "Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 2-23, February.
    4. Daniel Bienstock & Olga Raskina & Iraj Saniee & Qiong Wang, 2006. "Combined Network Design and Multiperiod Pricing: Modeling, Solution Techniques, and Computation," Operations Research, INFORMS, vol. 54(2), pages 261-276, April.
    5. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    6. Sara Mattia & Michael Poss, 2018. "A comparison of different routing schemes for the robust network loading problem: polyhedral results and computation," Computational Optimization and Applications, Springer, vol. 69(3), pages 753-800, April.
    7. Yogesh Kumar Agarwal & Prahalad Venkateshan, 2019. "New Valid Inequalities for the Optimal Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 268-284, April.
    8. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    9. Bhatt, Sneha Dhyani & Sinha, Ankur & Jayaswal, Sachin, 2024. "The capacitated r-hub interdiction problem with congestion: Models and solution approaches," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    10. Gunhak Lee & Ningchuan Xiao, 2009. "Examining the tradeoff between residential broadband service coverage and network connectivity using a bi‐objective facility location model," Papers in Regional Science, Wiley Blackwell, vol. 88(3), pages 547-562, August.
    11. M. Didi Biha & A.R. Mahjoub, 2000. "Steiner k-Edge Connected Subgraph Polyhedra," Journal of Combinatorial Optimization, Springer, vol. 4(1), pages 131-144, March.
    12. Frederick Kaefer & June S. Park, 1998. "Interconnecting LANs and a FDDI Backbone Using Transparent Bridges: A Model and Solution Algorithms," INFORMS Journal on Computing, INFORMS, vol. 10(1), pages 25-39, February.
    13. Ada Suk‐fung Ng & Trilochan Sastry & Janny M.Y. Leung & X.Q. Cai, 2004. "On the uncapacitated K‐commodity network design problem with zero flow‐costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(8), pages 1149-1172, December.
    14. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    15. Ioannis Gamvros & Bruce Golden & S. Raghavan, 2006. "The Multilevel Capacitated Minimum Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 348-365, August.
    16. Anantaram Balakrishnan & Prakash Mirchandani & Harihara Prasad Natarajan, 2009. "Connectivity Upgrade Models for Survivable Network Design," Operations Research, INFORMS, vol. 57(1), pages 170-186, February.
    17. van de Leensel, R.L.J.M. & Flippo, O.E. & Koster, Arie M.C.A. & Kolen, A.W.J., 1996. "A dynamic programming algorithm for the local access network expansion problem," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. Moon, Mark A. & Mentzer, John T. & Smith, Carlo D., 2003. "Conducting a sales forecasting audit," International Journal of Forecasting, Elsevier, vol. 19(1), pages 5-25.
    19. Agarwal, Y.K. & Aneja, Y.P., 2017. "Fixed charge multicommodity network design using p-partition facets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 124-135.
    20. Agarwal, Y.K. & Venkateshan, Prahalad, 2014. "Survivable network design with shared-protection routing," European Journal of Operational Research, Elsevier, vol. 238(3), pages 836-845.

    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:48:y:2000:i:6:p:866-877. 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.