論文の概要: Accelerating Generalized Benders Decomposition for Wireless Resource
Allocation
- arxiv url: http://arxiv.org/abs/2003.01294v2
- Date: Thu, 15 Oct 2020 01:11:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 23:37:49.284548
- Title: Accelerating Generalized Benders Decomposition for Wireless Resource
Allocation
- Title（参考訳）: 無線リソース割り当てのための一般化ベンダ分解の高速化
- Authors: Mengyuan Lee, Ning Ma, Guanding Yu, and Huaiyu Dai
- Abstract要約: 一般化ベンダー分解(英: Generalized Benders decomposition、GBD)は、混合整数非線形プログラミング(MINLP)問題に対する大域的最適アルゴリズムである。
本稿では、機械学習(ML)技術を活用し、マスター問題の複雑性の低減を目的としたGBDの高速化を提案する。
- 参考スコア（独自算出の注目度）: 40.75748765274763
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generalized Benders decomposition (GBD) is a globally optimal algorithm for
mixed integer nonlinear programming (MINLP) problems, which are NP-hard and can
be widely found in the area of wireless resource allocation. The main idea of
GBD is decomposing an MINLP problem into a primal problem and a master problem,
which are iteratively solved until their solutions converge. However, a direct
implementation of GBD is time- and memory-consuming. The main bottleneck is the
high complexity of the master problem, which increases over the iterations.
Therefore, we propose to leverage machine learning (ML) techniques to
accelerate GBD aiming at decreasing the complexity of the master problem.
Specifically, we utilize two different ML techniques, classification and
regression, to deal with this acceleration task. In this way, a cut classifier
and a cut regressor are learned, respectively, to distinguish between useful
and useless cuts. Only useful cuts are added to the master problem and thus the
complexity of the master problem is reduced. By using a resource allocation
problem in device-to-device communication networks as an example, we validate
that the proposed method can reduce the computational complexity of GBD without
loss of optimality and has strong generalization ability. The proposed method
is applicable for solving various MINLP problems in wireless networks since the
designs are invariant for different problems.
- Abstract（参考訳）: 一般化ベンダー分解(GBD)は、NPハードであり、無線リソース割り当ての領域で広く見られる混合整数非線形プログラミング(MINLP)問題に対して、グローバルに最適化されたアルゴリズムである。
GBDの主な考え方は、MINLP問題を原始問題とマスター問題に分解することであり、それらの解が収束するまで反復的に解決される。
しかし、GBDの直接実装は時間とメモリ消費である。
主なボトルネックは、マスター問題の複雑さが高く、イテレーションによって増加することです。
そこで本稿では,機械学習(ML)技術を活用し,マスター問題の複雑性の低減を目的としたGBDの高速化を提案する。
具体的には、このアクセラレーションタスクに対処するために、分類と回帰の2つの異なるML技術を利用する。
このようにして、カット分類器とカット回帰器をそれぞれ学習し、有用かつ無駄なカットを区別する。
有用なカットだけがマスター問題に追加され、マスター問題の複雑さが低減される。
デバイス間通信ネットワークにおけるリソース割り当て問題を例として、最適性を失わずにGBDの計算複雑性を低減し、強力な一般化能力を有することを示す。
提案手法は,異なる問題に対して設計が不変であるため,無線ネットワークにおける様々なminlp問題に対して適用可能である。
関連論文リスト
- Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳（メタデータ） (2023-10-24T06:22:20Z) - Hybrid Quantum-Classical General Benders Decomposition Algorithm for
Unit Commitment with Multiple Networked Microgrids [5.6035987109587895]
マルチネットワークマイクログリッド(UCMNM)によるユニットコミットは、典型的な混合整数非線形プログラミング問題である。
一般化ベンダー分解アルゴリズム(GBDA)フレームワークに量子コンピューティングを導入する。
プライバシー保護と独立意思決定のために、HQC-GBDAはUCMNM問題をマスター問題と一連のサブプロブレムに分解する。
論文 参考訳（メタデータ） (2022-10-13T02:26:27Z) - Large-scale matrix optimization based multi microgrid topology design
with a constrained differential evolution algorithm [30.792124441010447]
非線形問題を解くために二項行列に基づく微分進化アルゴリズムを提案する。
制約に対処するため,環境選択戦略を改良した実現可能性ルールを提案する。
論文 参考訳（メタデータ） (2022-07-18T00:35:29Z) - Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。
凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。
提案手法のパラメータはエンドツーエンドでトレーニング可能である。
論文 参考訳（メタデータ） (2021-06-30T08:57:01Z) - Deep Unsupervised Learning for Generalized Assignment Problems: A
Case-Study of User-Association in Wireless Networks [11.42707683459227]
本研究では,一般化代入問題(GAP)を時間効率良く解くために,DUL(Deep Unsupervised Learning)手法を提案する。
特に、カスタマイズされた損失関数を用いてディープニューラルネットワーク(DNN)のトレーニングを容易にする新しいアプローチを提案する。
数値実験の結果,提案手法は最適に近い結果をもたらし,時間・複雑さが著しく低下することが示された。
論文 参考訳（メタデータ） (2021-03-26T16:07:02Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。
ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。
本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
論文 参考訳（メタデータ） (2020-11-03T13:35:53Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z) - Graph Neural Networks for Scalable Radio Resource Management:
Architecture Design and Theoretical Analysis [31.372548374969387]
本稿では,大規模無線資源管理問題にグラフニューラルネットワーク(GNN)を適用することを提案する。
提案手法はスケーラビリティが高く,1つのGPU上で1,000ドルのトランシーバペアを6ミリ秒以内で行う干渉チャネルにおけるビームフォーミング問題を解くことができる。
論文 参考訳（メタデータ） (2020-07-15T11:43:32Z) - MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。
異種車両ルーティング問題に対するMineReduceの適用について述べる。
論文 参考訳（メタデータ） (2020-05-15T08:49:50Z) - Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
コミュニケーションのボトルネックは、大規模なディープラーニングにおいて重要な問題である。
非効率な分散問題に対する誤りフィードバックよりも優れた収束性を示す分散誤差フィードバック(DEF)アルゴリズムを提案する。
また、DEFよりも優れた境界を示すDEFの一般化を加速するDEFAを提案する。
論文 参考訳（メタデータ） (2020-04-11T03:50:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。