論文の概要: BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems
- arxiv url: http://arxiv.org/abs/2312.15864v1
- Date: Tue, 26 Dec 2023 03:09:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-27 16:10:56.260411
- Title: BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems
- Title(参考訳): BalMCTS:制約最適化問題に対するMCTSの目的関数と探索ノードのバランシング
- Authors: Yingkai Xiao, Jingjin Liu, Hankz Hankui Zhuo
- Abstract要約: 制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
- 参考スコア(独自算出の注目度): 7.196057722218442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constraint Optimization Problems (COP) pose intricate challenges in
combinatorial problems usually addressed through Branch and Bound (B\&B)
methods, which involve maintaining priority queues and iteratively selecting
branches to search for solutions. However, conventional approaches take a
considerable amount of time to find optimal solutions, and it is also crucial
to quickly identify a near-optimal feasible solution in a shorter time. In this
paper, we aim to investigate the effectiveness of employing a depth-first
search algorithm for solving COP, specifically focusing on identifying optimal
or near-optimal solutions within top $n$ solutions. Hence, we propose a novel
heuristic neural network algorithm based on MCTS, which, by simultaneously
conducting search and training, enables the neural network to effectively serve
as a heuristic during Backtracking. Furthermore, our approach incorporates
encoding COP problems and utilizing graph neural networks to aggregate
information about variables and constraints, offering more appropriate
variables for assignments. Experimental results on stochastic COP instances
demonstrate that our method identifies feasible solutions with a gap of less
than 17.63% within the initial 5 feasible solutions. Moreover, when applied to
attendant Constraint Satisfaction Problem (CSP) instances, our method exhibits
a remarkable reduction of less than 5% in searching nodes compared to
state-of-the-art approaches.
- Abstract(参考訳): 制約最適化問題(COP)は、通常はブランチとバウンド(B\&B)メソッドによって解決される組合せ問題において複雑な課題を提起する。
しかし、従来の手法では最適解を見つけるのにかなりの時間を要するため、より短時間で最適に近い解を素早く特定することが重要である。
本稿では, 最上位の$n$ 解における最適あるいは至近最適解の同定に焦点をあてた, 深さ優先探索アルゴリズムを用いたcopの解法の有効性について検討する。
そこで本研究では,mtsに基づく新しいヒューリスティックニューラルネットワークアルゴリズムを提案する。
さらに,本手法では,COP問題を符号化し,グラフニューラルネットワークを用いて変数や制約に関する情報を集約し,代入に適切な変数を提供する。
確率型COPの場合の実験結果から,本手法は初期5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
さらに, 適応制約満足度問題 (CSP) の事例に適用した場合, 探索ノードにおいて最先端の手法に比べて5%未満の顕著な減少率を示す。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
我々は,多目的最適化問題を解くために,近距離量子コンピュータを応用できる手法を開発した。
量子近似最適化アルゴリズム(QAOA)に基づく実装に焦点を当てる。
論文 参考訳(メタデータ) (2023-08-16T09:22:01Z) - Threshold-aware Learning to Generate Feasible Solutions for Mixed
Integer Programs [5.28005598366543]
ニューラルダイビング(ND)は、混合プログラム(MIP)における部分的な離散変数代入を生成する学習ベースのアプローチの1つである。
カバー範囲を最適化するためのポストホック法と学習に基づくアプローチを導入する。
実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。
論文 参考訳(メタデータ) (2023-08-01T07:03:16Z) - Simulation-guided Beam Search for Neural Combinatorial Optimization [13.072343634530883]
ニューラル最適化問題に対するシミュレーション誘導ビームサーチ(SGBS)を提案する。
我々は、SGBSと効率的なアクティブサーチ(EAS)を併用し、SGBSはEASでバックプロパゲーションされたソリューションの品質を高める。
提案手法をよく知られたCOベンチマークで評価し,SGBSが合理的な仮定で得られた解の質を著しく向上することを示す。
論文 参考訳(メタデータ) (2022-07-13T13:34:35Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective
Optimization Problems [0.0]
提案アルゴリズムは,実モデルのモデルによって定義される一連の代理問題の解法に基づく。
また,最適化ランドスケープのための最適なサロゲートモデルとナビゲーション戦略のメタ検索を行う。
論文 参考訳(メタデータ) (2021-03-19T11:18:03Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z) - Optimizing Wireless Systems Using Unsupervised and
Reinforced-Unsupervised Deep Learning [96.01176486957226]
無線ネットワークにおけるリソース割り当てとトランシーバーは、通常最適化問題の解決によって設計される。
本稿では,変数最適化と関数最適化の両問題を解くための教師なし・教師なし学習フレームワークを紹介する。
論文 参考訳(メタデータ) (2020-01-03T11:01:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。