Generalized Benders Decomposition to solve a nonlinear routing problem with queueing delay goal function

• Autorzy: Kozerski Kacper , Karbowski Andrzej

Identyfikatory

DOI

10.24425/ijet.2025.155486

• Języki publikacji: EN

Abstrakty

EN

We address the multicommodity flow problem with a nonlinear goal function modeling queueing delay. It is well-known that linear programming solvers perform better than those used for nonlinear programming. We can leverage their performance by employing the Generalized Benders Decomposition (GBD) to partition the problem into master and primal subproblems. We prove that in the case of multiple subproblems, which is true in our case, we can split both the optimality and feasibility cuts and add them independently. Moreover, we extended a known proof of convergence to enable a wider range of problems to be solved using GBD. We use the split cuts technique to precompute feasibility cuts and analytically solve the subproblems to omit the use of nonlinear optimization software. Furthermore, we explore the possibilities of starting point selection through linear and quadratic approximation. We carry out tests on a classical network example to show that GBD can sometimes outperform nonlinear solvers, and also that quadratic approximation for starting point selection can provide strictly better solution times, dominating commercial solvers.

Słowa kluczowe

EN

benders; GBD; optimization; decomposition; flow optimization; queueing delay

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 4
• Strony: 34
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Kozerski Kacper

• Warsaw University of Technology, Warsaw, Poland

autor

Karbowski Andrzej

• Warsaw University of Technology, Warsaw, Poland

Bibliografia

• [1] K. Salimifard and S. Bigharaz, “The multicommodity network flow problem: state of the art classification, applications, and solution methods,” Operational Research, vol. 22, no. 1, pp. 1-47, Mar. 2022. [Online]. Available: https://doi.org/10.1007/s12351-020-00564-8
• [2] M. Minoux, “Multicommodity Network Flow Models and Algorithms in Telecommunications,” in Handbook of Optimization in Telecommunications, M. G. C. Resende and P. M. Pardalos, Eds. Boston, MA: Springer US, 2006, pp. 163-184. [Online]. Available: https://doi.org/10.1007/978-0-387-30165-5_7
• [3] A. van den Nouweland, P. Borm, W. van Golstein Brouwers, R. Groot Bruinderink, and S. Tijs, “A Game Theoretic Approach to Problems in Telecommunication,” Management Science, vol. 42, no. 2, pp. 294-303, Feb. 1996, publisher: INFORMS. [Online]. Available: https://pubsonline.informs.org/doi/abs/10.1287/mnsc.42.2.294
• [4] M. Naserian and K. Tepe, “Game theoretic approach in routing protocol for wireless ad hoc networks,” Ad Hoc Networks, vol. 7, no. 3, pp. 569-578, May 2009. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1570870508000966
• [5] N. Hohn, D. Veitch, K. Papagiannaki, and C. Diot, “Bridging router performance and queuing theory,” SIGMETRICS Perform. Eval. Rev., vol. 32, no. 1, pp. 355-366, Jun. 2004. [Online]. Available: https://dl.acm.org/doi/10.1145/1012888.1005728
• [6] E. M. Gafni and D. P. Bertsekas, “Two-metric projection methods for constrained optimization,” SIAM Journal on Control and Optimization, vol. 22, no. 6, pp. 936-964, 1984. [Online]. Available: https://doi.org/10.1137/0322061
• [7] L. Layuan, L. Chunlin, and Y. Peiyan, “Performance evaluation and simulations of routing protocols in ad hoc networks,” Computer Communications, vol. 30, no. 8, pp. 1890-1898, Jun. 2007. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S014036640700103X
• [8] E. Amaldi, A. Capone, L. G. Gianoli, and L. Mascetti, “A MILP-Based Heuristic for Energy-Aware Traffic Engineering with Shortest Path Routing,” in Network Optimization, J. Pahl, T. Reiners, and S. Voß, Eds. Berlin, Heidelberg: Springer, 2011, pp. 464-477.
• [9] T. Larsson and N. Hedman, Routing protocols in wireless ad-hoc networks : a simulation study. Luleå University of Technology, 1998. [Online]. Available: https://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-52142
• [10] M. Fortin and R. Glowinski, “Chapter III On Decomposition-Coordination Methods Using an Augmented Lagrangian,” in Studies in Mathematics and Its Applications, ser. Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, M. Fortin and R. Glowinski, Eds. Elsevier, Jan. 1983, vol. 15, pp. 97-146. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0168202408700286
• [11] T. Larsson and D. Yuan, “An Augmented Lagrangian Algorithm for Large Scale Multicommodity Routing,” Computational Optimization and Applications, vol. 27, no. 2, pp. 187-215, Feb. 2004. [Online]. Available: https://doi.org/10.1023/B:COAP.0000008652.29295.eb
• [12] W. E. Wilhelm, “A Technical Review of Column Generation in Integer Programming,” Optimization and Engineering, vol. 2, no. 2, pp. 159-200, Jun. 2001. [Online]. Available: https://doi.org/10.1023/A:1013141227104
• [13] G. Carello, I. Filippini, S. Gualandi, and F. Malucelli, “Scheduling and routing in wireless multi-hop networks by column generation,” in Conference: International Network Optimization Conference (INOC), Jan. 2007.
• [14] D. A. Tarvin, R. K. Wood, and A. M. Newman, “Benders decomposition: Solving binary master problems by enumeration,” Operations Research Letters, vol. 44, no. 1, pp. 80-85, 2016. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167637715001558
• [15] A. M. Geoffrion, “Generalized Benders Decomposition,” Journal of Optimization Theory and Applications, vol. 10, no. 4, pp. 237-260, 10 1972. [Online]. Available: https://doi.org/10.1007/BF00934810
• [16] A. Karbowski, “Generalized Benders Decomposition method to solve big mixed-integer nonlinear optimization problems with convex objective and constraints functions,” Energies, vol. 14, no. 20, 2021. [Online]. Available: https://www.mdpi.com/1996-1073/14/20/6503
• [17] M. K. Awad, Y. Rafique, and R. A. M’Hallah, “Energy-aware routing for software-defined networks with discrete link rates: A Benders decomposition-based heuristic approach,” Sustainable Computing: Informatics and Systems, vol. 13, pp. 31-41, Mar. 2017. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2210537916301251
• [18] J. R. Birge and F. Louveaux, Two-Stage Recourse Problems. New York, NY: Springer New York, 2011, pp. 181-263. [Online]. Available: https://doi.org/10.1007/978-1-4614-0237-4_5
• [19] A. Jiménez-Cordero, J. M. Morales, and S. Pineda, “Warm-starting constraint generation for mixed-integer optimization: A Machine Learning approach,” Knowledge-Based Systems, vol. 253, p. 109570, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950705122007894