論文の概要: 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%未満の顕著な減少率を示す。
関連論文リスト
- Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
制約付き最適化のための学習型反復解法を提案する。
解法を特定のパラメトリック最適化問題にカスタマイズすることで、非常に高速で正確な解を得ることができる。
最適性のKarush-Kuhn-Tucker条件に基づく新しい損失関数を導入し、両ニューラルネットワークの完全な自己教師付きトレーニングを可能にする。
論文 参考訳（メタデータ） (2024-09-12T14:17:23Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
効率的な確率的選択に基づく制約付き多目的EAをPSCMOEAと呼ぶ。
a) 評価された解の実現可能性と収束状態に基づく適応探索境界同定スキームのような新しい要素を含む。
ECMOPを模擬する低評価予算を用いて, 幅広い制約付き問題に対して, 数値実験を行った。
論文 参考訳（メタデータ） (2024-05-22T02:32:58Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。