論文の概要: Predictive Machine Learning of Objective Boundaries for Solving COPs
- arxiv url: http://arxiv.org/abs/2111.03160v1
- Date: Thu, 4 Nov 2021 21:08:07 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-08 14:18:39.026807
- Title: Predictive Machine Learning of Objective Boundaries for Solving COPs
- Title（参考訳）: COP解法における目的境界の予測機械学習
- Authors: Helge Spieker, Arnaud Gotlieb
- Abstract要約: CPソルバをサポートするツールとして応用された境界推定フレームワークを提案する。
本枠組みでは, 境界推定に適したMLモデルについて検討し, 評価を行った。
以上の結果から,これらのCOPに対して,最小限のオーバーヘッドで準最適境界を学習できることが示唆された。
- 参考スコア（独自算出の注目度）: 21.206740640268283
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving Constraint Optimization Problems (COPs) can be dramatically
simplified by boundary estimation, that is, providing tight boundaries of cost
functions. By feeding a supervised Machine Learning (ML) model with data
composed of known boundaries and extracted features of COPs, it is possible to
train the model to estimate boundaries of a new COP instance. In this paper, we
first give an overview of the existing body of knowledge on ML for Constraint
Programming (CP) which learns from problem instances. Second, we introduce a
boundary estimation framework that is applied as a tool to support a CP solver.
Within this framework, different ML models are discussed and evaluated
regarding their suitability for boundary estimation, and countermeasures to
avoid unfeasible estimations that avoid the solver to find an optimal solution
are shown. Third, we present an experimental study with distinct CP solvers on
seven COPs. Our results show that near-optimal boundaries can be learned for
these COPs with only little overhead. These estimated boundaries reduce the
objective domain size by 60-88% and can help the solver to find near-optimal
solutions early during search.
- Abstract（参考訳）: 制約最適化問題(COP)の解法は,コスト関数の厳密な境界を与える境界推定によって劇的に単純化することができる。
監視された機械学習(ML)モデルに、既知の境界とCOPの特徴を抽出したデータを与えることで、新しいCOPインスタンスの境界を推定するようにモデルをトレーニングすることができる。
本稿ではまず,問題インスタンスから学習する制約プログラミング(CP)のためのMLに関する既存の知識体系の概要を紹介する。
第2に,cpソルバをサポートするツールとして適用する境界推定フレームワークを提案する。
本枠組みでは, 境界推定に適したMLモデルについて検討, 評価し, 最適解を見つけるための解法を避けるために, 実現不可能な推定を避ける対策を提示する。
第3に,異なるCPソルバを用いた7つのCOP実験を行った。
以上の結果から,これらのCOPに対してほぼ最適境界を学習できることが示唆された。
これらの推定境界は、対象のドメインサイズを60-88%削減し、探索の早い段階でほぼ最適解を見つけるのに役立つ。
関連論文リスト
- Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。
まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。
第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
論文 参考訳（メタデータ） (2024-10-24T15:26:14Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - 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) - Tight Guarantees for Interactive Decision Making with the
Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。
我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。
この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文 参考訳（メタデータ） (2023-01-19T18:24:08Z) - Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。
まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。
次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文 参考訳（メタデータ） (2022-08-17T18:49:53Z) - Linear programming-based solution methods for constrained POMDPs [0.5156484100374059]
制約付き部分観測可能なマルコフ決定過程(CPOMDP)は、様々な実世界の現象をモデル化するために用いられている。
我々は、CPOMDPの近似ポリシーを生成するために、グリッドベースの近似と線形プログラミング(LP)モデルを組み合わせる。
論文 参考訳（メタデータ） (2022-06-28T15:22:24Z) - Data-Driven Minimax Optimization with Expectation Constraints [9.373649142701803]
本稿では,最小値予測制約問題に対処するために,効率的な原始双対アルゴリズムのクラスを提案する。
我々のアルゴリズムは$mathcalO(frac1sqrtN)$の最適速度で収束することを示す。
論文 参考訳（メタデータ） (2022-02-16T05:23:27Z) - Conservative Distributional Reinforcement Learning with Safety
Constraints [22.49025480735792]
安全探索は、期待される長期コストが制約されるマルコフ決定問題とみなすことができる。
従来の非政治アルゴリズムは、制約付き最適化問題をラグランジアン緩和手法を導入して、対応する制約なしの双対問題に変換する。
本稿では,ポストリオ政策最適化による保守的分布最大化という,非政治的強化学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-18T19:45:43Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Learning Objective Boundaries for Constraint Optimization Problems [18.54162063161697]
タイトバウンダリは、探索空間をプルークしたり、問題特性を推定するのに役立ちます。
最適値を正しく過小評価する近接境界を見つけることは、COPを解くことなくほぼ不可能である。
本稿では,以前に解決されたCOPの事例から学習した境界推定のための新しい手法であるBionを紹介する。
論文 参考訳（メタデータ） (2020-06-20T12:09:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。