IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v210y2013i1p333-36010.1007-s10479-011-0962-8.html
   My bibliography  Save this article

A decomposition approach for solving a broadcast domination network design problem

Author

Listed:
  • Siqian Shen
  • J. Smith

Abstract

We consider an optimization problem that integrates network design and broadcast domination decisions. Given an undirected graph, a feasible broadcast domination is a set of nonnegative integer powers f i assigned to each node i, such that for any node j in the graph, there exists some node k having a positive f k -value whose shortest distance to node j is no more than f k . The cost of a broadcast domination solution is the sum of all node power values. The network design problem constructs edges that decrease the minimum broadcast domination cost on the graph. The overall problem we consider minimizes the sum of edge construction costs and broadcast domination costs. We show that this problem is NP-hard in the strong sense, even on unweighted graphs. We then propose a decomposition strategy, which iteratively adds valid inequalities based on optimal broadcast domination solutions corresponding to the first-stage network design solutions. We demonstrate that our decomposition approach is computationally far superior to the solution of a single large-scale mixed-integer programming formulation. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • Siqian Shen & J. Smith, 2013. "A decomposition approach for solving a broadcast domination network design problem," Annals of Operations Research, Springer, vol. 210(1), pages 333-360, November.
    • Handle: RePEc:spr:annopr:v:210:y:2013:i:1:p:333-360:10.1007/s10479-011-0962-8
    DOI: 10.1007/s10479-011-0962-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0962-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0962-8?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. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    2. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    3. Gilbert Laporte & François V. Louveaux & Luc van Hamme, 1994. "Exact Solution to a Location Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 28(2), pages 95-103, May.
    4. John Penuel & J. Cole Smith & Yang Yuan, 2010. "An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(5), pages 391-402, August.
    5. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    Full references (including those not matched with items on IDEAS)

    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. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    2. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    3. Fang, Kan & Wang, Shijin & Pinedo, Michael L. & Chen, Lin & Chu, Feng, 2021. "A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions," European Journal of Operational Research, Elsevier, vol. 291(1), pages 128-146.
    4. Kiho Seo & Seulgi Joung & Chungmok Lee & Sungsoo Park, 2022. "A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2804-2827, September.
    5. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    6. John Penuel & J. Cole Smith & Yang Yuan, 2010. "An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(5), pages 391-402, August.
    7. Simon Emde & Shohre Zehtabian & Yann Disser, 2023. "Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition," Annals of Operations Research, Springer, vol. 322(1), pages 467-496, March.
    8. Zhenzhen Zhang & Zhixing Luo & Roberto Baldacci & Andrew Lim, 2021. "A Benders Decomposition Approach for the Multivehicle Production Routing Problem with Order-up-to-Level Policy," Transportation Science, INFORMS, vol. 55(1), pages 160-178, 1-2.
    9. Leutwiler, Florin & Corman, Francesco, 2022. "A logic-based Benders decomposition for microscopic railway timetable planning," European Journal of Operational Research, Elsevier, vol. 303(2), pages 525-540.
    10. Elvin Coban & J. Hooker, 2013. "Single-facility scheduling by logic-based Benders decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 245-272, November.
    11. Sun, Defeng & Tang, Lixin & Baldacci, Roberto & Lim, Andrew, 2021. "An exact algorithm for the unidirectional quay crane scheduling problem with vessel stability," European Journal of Operational Research, Elsevier, vol. 291(1), pages 271-283.
    12. Jean-François Côté & Mauro Dell'Amico & Manuel Iori, 2014. "Combinatorial Benders' Cuts for the Strip Packing Problem," Operations Research, INFORMS, vol. 62(3), pages 643-661, June.
    13. Heiko Diefenbach & Simon Emde & Christoph H. Glock & Eric H. Grosse, 2022. "New solution procedures for the order picker routing problem in U-shaped pick areas with a movable depot," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 535-573, June.
    14. Boysen, Nils & Emde, Simon & Schwerdfeger, Stefan, 2022. "Crowdshipping by employees of distribution centers: Optimization approaches for matching supply and demand," European Journal of Operational Research, Elsevier, vol. 296(2), pages 539-556.
    15. Sun, Defeng & Tang, Lixin & Baldacci, Roberto, 2019. "A Benders decomposition-based framework for solving quay crane scheduling problems," European Journal of Operational Research, Elsevier, vol. 273(2), pages 504-515.
    16. Aliza Heching & J. N. Hooker & Ryo Kimura, 2019. "A Logic-Based Benders Approach to Home Healthcare Delivery," Transportation Science, INFORMS, vol. 53(2), pages 510-522, March.
    17. Senay Solak & Christina Scherrer & Ahmed Ghoniem, 2014. "The stop-and-drop problem in nonprofit food distribution networks," Annals of Operations Research, Springer, vol. 221(1), pages 407-426, October.
    18. Jean-François Côté & Mohamed Haouari & Manuel Iori, 2021. "Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 963-978, July.
    19. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    20. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.

    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:spr:annopr:v:210:y:2013:i:1:p:333-360:10.1007/s10479-011-0962-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.