論文の概要: Solving Bilevel Knapsack Problem using Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2211.13436v1
- Date: Thu, 24 Nov 2022 06:36:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 15:32:46.965684
- Title: Solving Bilevel Knapsack Problem using Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークを用いた二値クナップサック問題の解法
- Authors: Sunhyeon Kwon, Sungsoo Park
- Abstract要約: グラフニューラルネットワークを用いた深層学習手法を提案し,二段階クナップサック問題の解法を提案する。
我々のモデルは、最適ギャップが1.7%の正確なアルゴリズムの約500倍高速な実現可能な解を発見した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Bilevel Optimization Problem is a hierarchical optimization problem with
two agents, a leader and a follower. The leader make their own decisions first,
and the followers make the best choices accordingly. The leader knows the
information of the followers, and the goal of the problem is to find the
optimal solution by considering the reactions of the followers from the
leader's point of view. For the Bilevel Optimization Problem, there are no
general and efficient algorithms or commercial solvers to get an optimal
solution, and it is very difficult to get a good solution even for a simple
problem. In this paper, we propose a deep learning approach using Graph Neural
Networks to solve the bilevel knapsack problem. We train the model to predict
the leader's solution and use it to transform the hierarchical optimization
problem into a single-level optimization problem to get the solution. Our model
found the feasible solution that was about 500 times faster than the exact
algorithm with $1.7\%$ optimal gap. Also, our model performed well on problems
of different size from the size it was trained on.
- Abstract（参考訳）: 双レベル最適化問題は、リーダーとフォロワーの2人のエージェントによる階層的最適化問題である。
リーダーはまず自分の決定を下し、フォロワーはそれに従って最良の選択をする。
リーダーはフォロワーの情報を知っており、問題の目標は、リーダーの視点からフォロワーの反応を考慮して最適な解決策を見つけることである。
双レベル最適化問題では、最適解を得るための汎用的で効率的なアルゴリズムや商用解法は存在せず、単純な問題であっても良い解を得るのは非常に困難である。
本稿では,グラフニューラルネットワークを用いた2レベルナップサック問題を解くための深層学習手法を提案する。
リーダーのソリューションを予測するためにモデルをトレーニングし、階層的な最適化問題を単一レベルの最適化問題に変換するためにそれを使用します。
我々のモデルは、最適ギャップが1.7\%の正確なアルゴリズムよりも500倍高速な実現可能な解を発見した。
また、トレーニングしたサイズとサイズが異なる問題に対して、我々のモデルはよく機能しました。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。
本稿では,GNNを組合せ最適化問題に適用できることを示す。
論文 参考訳（メタデータ） (2024-01-11T01:15:28Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
Natural Language for Optimization (NL4Opt) NeurIPS 2022コンペティションでは、最適化ソルバのアクセシビリティとユーザビリティの改善に重点を置いている。
本稿では,チームのソリューションについて述べる。
提案手法は,サブタスク1のF1スコアとサブタスク2の0.867の精度を達成し,それぞれ第4位,第3位を獲得した。
論文 参考訳（メタデータ） (2023-02-09T13:57:06Z) - Learning to repeatedly solve routing problems [5.08128537391027]
データのマイナーチェンジ後に問題の再最適化について学習した。
元のソリューションのエッジを考慮すれば、最適なソリューションに留まる確率の高いソリューションを予測し、修正することが目標です。
この解の偏差予測は問題の複雑さを減らし、解を高速化する。
論文 参考訳（メタデータ） (2022-12-15T19:33:54Z) - Machine Learning for K-adaptability in Two-stage Robust Optimization [0.40964539027092906]
2段階の頑健な最適化問題は、最も難しい最適化問題の1つである。
このクラスの問題の解の1つは、K適応性である。
機械学習に基づくノード選択戦略を提案する。
論文 参考訳（メタデータ） (2022-10-20T10:43:23Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-06-02T13:54:27Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳（メタデータ） (2020-02-20T17:07:08Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳（メタデータ） (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。