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. 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.
    2. 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.
    3. 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.
    4. 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).
    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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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).
    12. 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.
    13. 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.
    14. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.
    15. Geir Dahl & Alexander Martin & Mechthild Stoer, 1999. "Routing Through Virtual Paths in Layered Telecommunication Networks," Operations Research, INFORMS, vol. 47(5), pages 693-702, October.
    16. Juan Ma & Balabhaskar Balasundaram, 2019. "On the chance-constrained minimum spanning k-core problem," Journal of Global Optimization, Springer, vol. 74(4), pages 783-801, August.
    17. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    18. Young-Soo Myung & Hyun-joon Kim & Dong-wan Tcha, 1999. "Design of Communication Networks with Survivability Constraints," Management Science, INFORMS, vol. 45(2), pages 238-252, February.
    19. Konak, Abdullah & Bartolacci, Michael R., 2007. "Designing survivable resilient networks: A stochastic hybrid genetic algorithm approach," Omega, Elsevier, vol. 35(6), pages 645-658, December.
    20. Majid Taghavi & Kai Huang, 2016. "A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 600-614, December.

    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.