| Presentation | 2021-03-15 Approximate solution of the communication link load balancing problem using the lagrangian relaxation method Daichi Shimizu, Fumiya Onogi, Norihiko Shinomiya, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This study has focused on the UELB problem that aims at leveling the traffic load of a communication link in an information network by determining the path of a flow that minimizes the maximum load factor of the link. The UELB problem has been proved to be NP-hard, and an approximate solution method using the LP relaxation has been proposed to verify the results. This paper proposes another algorithm using the Lagrangian relaxation method in order to objectively evaluate the accuracy of the approximate solutions obtained so far. We have conducted comparison experiments with the method using LP relaxation. The result has demonstrated that the proposed algorithm has relatively higher computational complexity and taken a long time to calculate the solution because of using the subgradient method for the Lagrangian relaxation. In addition, the weakened constraints lead to resulting in a high traffic load factor, which indicates that the conventional LP relaxation is more effective. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Network flow problem / Lagrangian relaxation method / Subgradient method |
| Paper # | MSS2020-44 |
| Date of Issue | 2021-03-08 (MSS) |
| Conference Information | |
| Committee | NLP / MSS |
|---|---|
| Conference Date | 2021/3/15(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | MSS, NLP, Work In Progress (MSS only), and etc. |
| Chair | Kiyohisa Natsume(Kyushu Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) |
| Vice Chair | Takuji Kosaka(Chukyo Univ.) / Atsuo Ozaki(Osaka Inst. of Tech.) |
| Secretary | Takuji Kosaka(Kyushu Inst. of Tech.) / Atsuo Ozaki(Kagawa Univ.) |
| Assistant | Toshikaza Samura(Yamaguchi Univ.) / Hideyuki Kato(Oita Univ.) / Naoki Hayashi(Osaka Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Nonlinear Problems / Technical Committee on Mathematical Systems Science and its Applications |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Approximate solution of the communication link load balancing problem using the lagrangian relaxation method |
| Sub Title (in English) | |
| Keyword(1) | Network flow problem |
| Keyword(2) | Lagrangian relaxation method |
| Keyword(3) | Subgradient method |
| 1st Author's Name | Daichi Shimizu |
| 1st Author's Affiliation | Soka University(Soka Univ) |
| 2nd Author's Name | Fumiya Onogi |
| 2nd Author's Affiliation | Soka University(Soka Univ) |
| 3rd Author's Name | Norihiko Shinomiya |
| 3rd Author's Affiliation | Soka University(Soka Univ) |
| Date | 2021-03-15 |
| Paper # | MSS2020-44 |
| Volume (vol) | vol.120 |
| Number (no) | MSS-429 |
| Page | pp.pp.5-9(MSS), |
| #Pages | 5 |
| Date of Issue | 2021-03-08 (MSS) |