An exact column generation algorithm for load balancing in capacity sharing networks
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929609221603328 |
|---|---|
| author | Hu, Kaixiang Huang, Feilong Kou, Caixia |
| author_facet | Hu, Kaixiang Huang, Feilong Kou, Caixia |
| contents | Capacity sharing networks are typical heterogeneous communication networks widely applied in information and communications technology (ICT) field. In such networks, resources like bandwidth, spectrum, computation and storage are shared among various communication services. Meanwhile, the issue of network congestion is always a prominent challenge. To handle network congestion essentially needs to solve the load balancing of networks. In this paper, for capacity sharing networks, we formulate their load balancing problem as a maximum multi-commodity flow problem. For such a problem, always a large-scale linear programming, the column generation algorithm is a commonly used and crucial method to solve it. In each iteration, this algorithm involves solving a linear programming subproblem and determining whether to terminate or generate a new column for inclusion in the subproblem. This iterative procedure of solving and checking continues throughout the algorithm. Nevertheless, since the checking subproblem is NP-hard, its solution significantly impacts the overall efficiency of the algorithm. In this paper, we innovatively convert the checking subproblem into a single-constrained shortest path (SCSP) subproblem. By exactly solving the SCSP subproblem, we can obtain the optimal solution to the checking subproblem with same or less computing time. Experimental results demonstrate that our algorithm achieves computational efficiency comparable to heuristic algorithms while outperforming other state-of-the-art algorithms by at least an order of magnitude. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00555 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An exact column generation algorithm for load balancing in capacity sharing networks Hu, Kaixiang Huang, Feilong Kou, Caixia Optimization and Control Systems and Control Capacity sharing networks are typical heterogeneous communication networks widely applied in information and communications technology (ICT) field. In such networks, resources like bandwidth, spectrum, computation and storage are shared among various communication services. Meanwhile, the issue of network congestion is always a prominent challenge. To handle network congestion essentially needs to solve the load balancing of networks. In this paper, for capacity sharing networks, we formulate their load balancing problem as a maximum multi-commodity flow problem. For such a problem, always a large-scale linear programming, the column generation algorithm is a commonly used and crucial method to solve it. In each iteration, this algorithm involves solving a linear programming subproblem and determining whether to terminate or generate a new column for inclusion in the subproblem. This iterative procedure of solving and checking continues throughout the algorithm. Nevertheless, since the checking subproblem is NP-hard, its solution significantly impacts the overall efficiency of the algorithm. In this paper, we innovatively convert the checking subproblem into a single-constrained shortest path (SCSP) subproblem. By exactly solving the SCSP subproblem, we can obtain the optimal solution to the checking subproblem with same or less computing time. Experimental results demonstrate that our algorithm achieves computational efficiency comparable to heuristic algorithms while outperforming other state-of-the-art algorithms by at least an order of magnitude. |
| title | An exact column generation algorithm for load balancing in capacity sharing networks |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2411.00555 |