Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition
We discuss several algorithms for solving a network optimization problem of simultaneous routing and bandwidth allocation in green networks in a decomposed way, based on the augmented Lagrangian. The problem is difficult due to the nonconvexity caused by binary routing variables. The chosen algorith...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2024-03-01
|
Series: | Energies |
Subjects: | |
Online Access: | https://www.mdpi.com/1996-1073/17/5/1233 |
_version_ | 1797264612362551296 |
---|---|
author | Anthony Chukwuemeka Nwachukwu Andrzej Karbowski |
author_facet | Anthony Chukwuemeka Nwachukwu Andrzej Karbowski |
author_sort | Anthony Chukwuemeka Nwachukwu |
collection | DOAJ |
description | We discuss several algorithms for solving a network optimization problem of simultaneous routing and bandwidth allocation in green networks in a decomposed way, based on the augmented Lagrangian. The problem is difficult due to the nonconvexity caused by binary routing variables. The chosen algorithms, which are several versions of the Multiplier Method, including the Alternating Direction Method of Multipliers (ADMM), have been implemented in Python and tested on several networks’ data. We derive theoretical formulations for the inequality constraints of the Bertsekas, Tatjewski and SALA methods, formulated originally for problems with equality constraints. We also introduce some modifications to the Bertsekas and Tatjewski methods, without which they do not work for an MINLP problem. The final comparison of the performance of these algorithms shows a significant advantage of the augmented Lagrangian algorithms, using decomposition for big problems. In our particular case of the simultaneous routing and bandwidth allocation problem, these algorithms seem to be the best choice. |
first_indexed | 2024-04-25T00:31:40Z |
format | Article |
id | doaj.art-e7bf16fe3219479987e6f2ffecc089a8 |
institution | Directory Open Access Journal |
issn | 1996-1073 |
language | English |
last_indexed | 2024-04-25T00:31:40Z |
publishDate | 2024-03-01 |
publisher | MDPI AG |
record_format | Article |
series | Energies |
spelling | doaj.art-e7bf16fe3219479987e6f2ffecc089a82024-03-12T16:43:49ZengMDPI AGEnergies1996-10732024-03-01175123310.3390/en17051233Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and DecompositionAnthony Chukwuemeka Nwachukwu0Andrzej Karbowski1Doctoral School, Warsaw University of Technology, Pl. Politechniki 1, 00-661 Warsaw, PolandFaculty of Electronics and Information Technology, Institute of Control and Computation Engineering, Warsaw University of Technology, ul. Nowowiejska 15/19, 00-665 Warsaw, PolandWe discuss several algorithms for solving a network optimization problem of simultaneous routing and bandwidth allocation in green networks in a decomposed way, based on the augmented Lagrangian. The problem is difficult due to the nonconvexity caused by binary routing variables. The chosen algorithms, which are several versions of the Multiplier Method, including the Alternating Direction Method of Multipliers (ADMM), have been implemented in Python and tested on several networks’ data. We derive theoretical formulations for the inequality constraints of the Bertsekas, Tatjewski and SALA methods, formulated originally for problems with equality constraints. We also introduce some modifications to the Bertsekas and Tatjewski methods, without which they do not work for an MINLP problem. The final comparison of the performance of these algorithms shows a significant advantage of the augmented Lagrangian algorithms, using decomposition for big problems. In our particular case of the simultaneous routing and bandwidth allocation problem, these algorithms seem to be the best choice.https://www.mdpi.com/1996-1073/17/5/1233nonconvex optimizationaugmented Lagrangianmultiplier methodalternating direction method of multipliersseparable problemsnetwork optimization |
spellingShingle | Anthony Chukwuemeka Nwachukwu Andrzej Karbowski Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition Energies nonconvex optimization augmented Lagrangian multiplier method alternating direction method of multipliers separable problems network optimization |
title | Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition |
title_full | Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition |
title_fullStr | Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition |
title_full_unstemmed | Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition |
title_short | Solution of the Simultaneous Routing and Bandwidth Allocation Problem in Energy-Aware Networks Using Augmented Lagrangian-Based Algorithms and Decomposition |
title_sort | solution of the simultaneous routing and bandwidth allocation problem in energy aware networks using augmented lagrangian based algorithms and decomposition |
topic | nonconvex optimization augmented Lagrangian multiplier method alternating direction method of multipliers separable problems network optimization |
url | https://www.mdpi.com/1996-1073/17/5/1233 |
work_keys_str_mv | AT anthonychukwuemekanwachukwu solutionofthesimultaneousroutingandbandwidthallocationprobleminenergyawarenetworksusingaugmentedlagrangianbasedalgorithmsanddecomposition AT andrzejkarbowski solutionofthesimultaneousroutingandbandwidthallocationprobleminenergyawarenetworksusingaugmentedlagrangianbasedalgorithmsanddecomposition |