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. 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.
    2. Koot, Martijn & Wijnhoven, Fons, 2021. "Usage impact on data center electricity needs: A system dynamic forecasting model," Applied Energy, Elsevier, vol. 291(C).
    3. 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.
    4. 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.
    5. 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.
    6. Duan Li & Xiaoling Sun, 2006. "Nonlinear Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-32995-6, September.
    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. 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.
    3. 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).
    4. 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.
    5. 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.
    6. 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).
    7. 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.
    8. 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.
    9. 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.
    10. 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).
    11. 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.
    12. 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.
    13. Kouhei Harada, 2021. "A Feasibility-Ensured Lagrangian Heuristic for General Decomposable Problems," SN Operations Research Forum, Springer, vol. 2(4), pages 1-26, December.
    14. Lin, Yun Hui & Wang, Yuan & Lee, Loo Hay & Chew, Ek Peng, 2022. "Omnichannel facility location and fulfillment optimization," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 187-209.
    15. Wang, Kaifeng & Ye, Lin & Yang, Shihui & Deng, Zhanfeng & Song, Jieying & Li, Zhuo & Zhao, Yongning, 2023. "A hierarchical dispatch strategy of hybrid energy storage system in internet data center with model predictive control," Applied Energy, Elsevier, vol. 331(C).
    16. Zehua Yu & Zheng Li & Linwei Ma, 2023. "Strategies for the Resilience of Power-Coal Supply Chains in Low-Carbon Energy Transition: A System Dynamics Model and Scenario Analysis of China up to 2060," Sustainability, MDPI, vol. 15(9), pages 1-19, April.
    17. Alidaee, Bahram, 2014. "Zero duality gap in surrogate constraint optimization: A concise review of models," European Journal of Operational Research, Elsevier, vol. 232(2), pages 241-248.
    18. Pizzolato, Alberto & Sciacovelli, Adriano & Verda, Vittorio, 2019. "Centralized control of district heating networks during failure events using discrete adjoint sensitivities," Energy, Elsevier, vol. 184(C), pages 58-72.
    19. Eguía Ribero, María Isabel & Garín Martín, María Araceli & Unzueta Inchaurbe, Aitziber, 2018. "Generating cluster submodels from two-stage stochastic mixed integer optimization models," BILTOKI 31248, Universidad del País Vasco - Departamento de Economía Aplicada III (Econometría y Estadística).

    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.