| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-03-15 11:10 ラグランジュ緩和法を用いた通信リンク負荷平準化問題の近似解法 ○清水大智・大野木文弥・篠宮紀彦（創価大）  MSS2020-44 |
|
| 抄録 | （和） | 本研究では，情報通信ネットワークにおけるリンクのトラヒック負荷を平準化することを目的とし，リンクの最大負荷率を最小化するフローの経路を決定するUELB問題を対象としてきた．これまで，UELB問題はNP困難であることが証明されており，LP緩和を用いた近似解法を提案し，結果の検証を進めてきた．本稿では，これまで得られてきた近似解の精度を客観的に評価するため，ラグランジュ緩和法を用いた別のアルゴリズムを提案し，LP緩和による手法との比較実験を行った．結果として，今回，提案したアルゴリズムは，ラグランジュ緩和を行う際に劣勾配法を用いたため，計算量が比較的多くなり，解の算出に時間がかかった．さらに，制約も弱くなったため，トラヒック負荷率も高い値となり，従来のLP緩和の方が有効であることが示された． |
| （英） | 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. | |
| キーワード | （和） | ネットワークフロー問題 / ラグランジュ緩和法 / 劣勾配法 / / / / / |
| （英） | Network flow problem / Lagrangian relaxation method / Subgradient method / / / / / | |
| 文献情報 | 信学技報, vol. 120, no. 429, MSS2020-44, pp. 5-9, 2021年3月. | |
| 資料番号 | MSS2020-44 | |
| 発行日 | 2021-03-08 (MSS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | MSS2020-44 |
|
| 研究会情報 | |
| 研究会 | NLP MSS |
| 開催期間 | 2021-03-15 - 2021-03-16 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | MSS，NLP，一般，およびWIP（MSSのみ） |
| テーマ（英） | MSS, NLP, Work In Progress (MSS only), and etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2021-03-NLP-MSS |
| 本文の言語 | 日本語 |
| タイトル（和） | ラグランジュ緩和法を用いた通信リンク負荷平準化問題の近似解法 |
| サブタイトル（和） | |
| タイトル（英） | Approximate solution of the communication link load balancing problem using the lagrangian relaxation method |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ネットワークフロー問題 / Network flow problem |
| キーワード(2)（和/英） | ラグランジュ緩和法 / Lagrangian relaxation method |
| キーワード(3)（和/英） | 劣勾配法 / Subgradient method |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 清水 大智 / Daichi Shimizu / シミズ ダイチ |
| 第1著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ) |
| 第2著者 氏名（和/英/ヨミ） | 大野木 文弥 / Fumiya Onogi / オオノギ フミヤ |
| 第2著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ) |
| 第3著者 氏名（和/英/ヨミ） | 篠宮 紀彦 / Norihiko Shinomiya / シノミヤ ノリヒコ |
| 第3著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-03-15 11:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | MSS2020-44 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.429 |
| ページ範囲 | pp.5-9 |
| ページ数 | 5 |
| 発行日 | 2021-03-08 (MSS) |
[研究会発表申込システムのトップページに戻る]