IDEAS home Printed from https://ideas.repec.org/a/gam/jeners/v15y2022i20p7634-d943645.html
   My bibliography  Save this article

Decomposition Methods for the Network Optimization Problem of Simultaneous Routing and Bandwidth Allocation Based on Lagrangian Relaxation

Author

Listed:
  • Ihnat Ruksha

    (Faculty of Electronics and Information Technology, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland)

  • Andrzej Karbowski

    (Institute of Control and Computation Engineering, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warsaw, Poland)

Abstract

The main purpose of the work was examining various methods of decomposition of a network optimization problem of simultaneous routing and bandwidth allocation based on Lagrangian relaxation. The problem studied is an NP-hard mixed-integer nonlinear optimization problem. Multiple formulations of the optimization problem are proposed for the problem decomposition. The decomposition methods used several problem formulations and different choices of the dualized constraints. A simple gradient coordination algorithm, cutting-plane coordination algorithm, and their more sophisticated variants were used to solve dual problems. The performance of the proposed decomposition methods was compared to the commercial solver CPLEX and a heuristic algorithm.

Suggested Citation

  • Ihnat Ruksha & Andrzej Karbowski, 2022. "Decomposition Methods for the Network Optimization Problem of Simultaneous Routing and Bandwidth Allocation Based on Lagrangian Relaxation," Energies, MDPI, vol. 15(20), pages 1-28, October.
    • Handle: RePEc:gam:jeners:v:15:y:2022:i:20:p:7634-:d:943645
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1996-1073/15/20/7634/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1996-1073/15/20/7634/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. An, Shi & Cui, Na & Bai, Yun & Xie, Weijun & Chen, Mingliu & Ouyang, Yanfeng, 2015. "Reliable emergency service facility location under facility disruption, en-route congestion and in-facility queuing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 199-216.
    2. Zhang, Yufeng & Khani, Alireza, 2019. "An algorithm for reliable shortest path problem with travel time correlations," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 92-113.
    3. Ahmadi-Javid, Amir & Hoseinpour, Pooya, 2019. "Service system design for managing interruption risks: A backup-service risk-mitigation strategy," European Journal of Operational Research, Elsevier, vol. 274(2), pages 417-431.
    4. Duan Li & Xiaoling Sun, 2006. "Nonlinear Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-32995-6, April.
    5. Komeyl Baghizadeh & Julia Pahl & Guiping Hu, 2021. "Closed-Loop Supply Chain Design with Sustainability Aspects and Network Resilience under Uncertainty: Modelling and Application," Mathematical Problems in Engineering, Hindawi, vol. 2021, pages 1-23, September.
    6. Koot, Martijn & Wijnhoven, Fons, 2021. "Usage impact on data center electricity needs: A system dynamic forecasting model," Applied Energy, Elsevier, vol. 291(C).
    7. Ghaddar, Bissan & Naoum-Sawaya, Joe & Kishimoto, Akihiro & Taheri, Nicole & Eck, Bradley, 2015. "A Lagrangian decomposition approach for the pump scheduling problem in water networks," European Journal of Operational Research, Elsevier, vol. 241(2), pages 490-501.
    8. Andrzej Karbowski, 2021. "Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions," Energies, MDPI, vol. 14(20), pages 1-18, October.
    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. Anthony Chukwuemeka Nwachukwu & Andrzej Karbowski, 2024. "Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition," Energies, MDPI, vol. 17(5), pages 1-23, March.
    2. Ghaddar, Bissan & Claeys, Mathieu & Mevissen, Martin & Eck, Bradley J., 2017. "Polynomial optimization for water networks: Global solutions for the valve setting problem," European Journal of Operational Research, Elsevier, vol. 261(2), pages 450-459.
    3. Bohong Wang & Yongtu Liang & Wei Zhao & Yun Shen & Meng Yuan & Zhimin Li & Jian Guo, 2021. "A Continuous Pump Location Optimization Method for Water Pipe Network Design," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 35(2), pages 447-464, January.
    4. Yi Zheng & Li Liu & Victor Shi & Wenxing Huang & Jianxiu Liao, 2022. "A Resilience Analysis of a Medical Mask Supply Chain during the COVID-19 Pandemic: A Simulation Modeling Approach," IJERPH, MDPI, vol. 19(13), pages 1-21, June.
    5. Jie, Ke-Wei & Liu, San-Yang & Sun, Xiao-Jun & Xu, Yun-Cheng, 2023. "A dynamic ripple-spreading algorithm for solving mean–variance of shortest path model in uncertain random networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    6. Babasola Osibo & Simisola Adamo, 2023. "Data Centers and Green Energy: Paving the Way for a Sustainable Digital Future," International Journal of Latest Technology in Engineering, Management & Applied Science, International Journal of Latest Technology in Engineering, Management & Applied Science (IJLTEMAS), vol. 12(11), pages 15-30, November.
    7. Miguel Reyna-Castillo & Alejandro Santiago & Salvador Ibarra Martínez & José Antonio Castán Rocha, 2022. "Social Sustainability and Resilience in Supply Chains of Latin America on COVID-19 Times: Classification Using Evolutionary Fuzzy Knowledge," Mathematics, MDPI, vol. 10(14), pages 1-18, July.
    8. Guo, Jian-Xin & Huang, Chen, 2020. "Feasible roadmap for CCS retrofit of coal-based power plants to reduce Chinese carbon emissions by 2050," Applied Energy, Elsevier, vol. 259(C).
    9. Jorge A. Sefair & Oscar Guaje & Andrés L. Medaglia, 2021. "A column-oriented optimization approach for the generation of correlated random vectors," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 777-808, September.
    10. Du, Juntao & Shen, Zhiyang & Song, Malin & Zhang, Linda, 2023. "Nexus between digital transformation and energy technology innovation: An empirical test of A-share listed enterprises," Energy Economics, Elsevier, vol. 120(C).
    11. Cascón, J.M. & González-Arteaga, T. & de Andrés Calle, R., 2019. "Reaching social consensus family budgets: The Spanish case," Omega, Elsevier, vol. 86(C), pages 28-41.
    12. Wang, Zhaodong & Xie, Siyang & Ouyang, Yanfeng, 2022. "Planning reliable service facility location against disruption risks and last-mile congestion in a continuous space," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 123-140.
    13. Fatima Bellahcene, 2019. "Application of the polyblock method to special integer chance constrained problem," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 29(4), pages 23-40.
    14. Chunli Liu & Jianjun Gao, 2015. "A polynomial case of convex integer quadratic programming problems with box integer constraints," Journal of Global Optimization, Springer, vol. 62(4), pages 661-674, August.
    15. Vitale, Ignacio & Dondo, Rodolfo G. & González, Matías & Cóccola, Mariana E., 2022. "Modelling and optimization of material flows in the wood pellet supply chain," Applied Energy, Elsevier, vol. 313(C).
    16. Chen, Xiaoyuan & Jiang, Shan & Chen, Yu & Lei, Yi & Zhang, Donghui & Zhang, Mingshun & Gou, Huayu & Shen, Boyang, 2022. "A 10 MW class data center with ultra-dense high-efficiency energy distribution: Design and economic evaluation of superconducting DC busbar networks," Energy, Elsevier, vol. 250(C).
    17. Xiaoli Feng & Baoyun Qiu & Yongxing Wang, 2020. "Optimizing Parallel Pumping Station Operations in an Open-Channel Water Transfer System Using an Efficient Hybrid Algorithm," Energies, MDPI, vol. 13(18), pages 1-19, September.
    18. L. Escudero & M. Garín & G. Pérez & A. Unzueta, 2012. "Lagrangian Decomposition for large-scale two-stage stochastic mixed 0-1 problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(2), pages 347-374, July.
    19. Ouyang, Yanfeng & Wang, Zhaodong & Yang, Hai, 2015. "Facility location design under continuous traffic equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 18-33.

    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:gam:jeners:v:15:y:2022:i:20:p:7634-:d:943645. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.