論文の概要: Learning Objective Boundaries for Constraint Optimization Problems

• arxiv url: http://arxiv.org/abs/2006.11560v1
• Date: Sat, 20 Jun 2020 12:09:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 22:45:52.449625
• Title: Learning Objective Boundaries for Constraint Optimization Problems
• Title（参考訳）: 制約最適化問題に対する目的境界の学習
• Authors: Helge Spieker, Arnaud Gotlieb
• Abstract要約: タイトバウンダリは、探索空間をプルークしたり、問題特性を推定するのに役立ちます。 最適値を正しく過小評価する近接境界を見つけることは、COPを解くことなくほぼ不可能である。 本稿では,以前に解決されたCOPの事例から学習した境界推定のための新しい手法であるBionを紹介する。
• 参考スコア（独自算出の注目度）: 18.54162063161697
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constraint Optimization Problems (COP) are often considered without sufficient knowledge on the boundaries of the objective variable to optimize. When available, tight boundaries are helpful to prune the search space or estimate problem characteristics. Finding close boundaries, that correctly under- and overestimate the optimum, is almost impossible without actually solving the COP. This paper introduces Bion, a novel approach for boundary estimation by learning from previously solved instances of the COP. Based on supervised machine learning, Bion is problem-specific and solver-independent and can be applied to any COP which is repeatedly solved with different data inputs. An experimental evaluation over seven realistic COPs shows that an estimation model can be trained to prune the objective variables' domains by over 80%. By evaluating the estimated boundaries with various COP solvers, we find that Bion improves the solving process for some problems, although the effect of closer bounds is generally problem-dependent.
• Abstract（参考訳）: 制約最適化問題(COP)は、最適化する目的変数の境界について十分な知識を持たないと考えられることが多い。 利用可能な場合、厳密な境界は、探索空間を掘り起こしたり、問題特性を推定するのに役立ちます。 最適値を正しく過小評価する近接境界を見つけることは、COPを実際に解くことなくほぼ不可能である。 本稿では,以前に解決されたCOPの事例から学習した境界推定手法であるBionを紹介する。 教師付き機械学習に基づいて、Bionは問題固有であり、ソルバ非依存であり、異なるデータ入力で繰り返し解決される任意のCOPに適用することができる。 7つの現実的なCOPに対して実験的に評価した結果,対象変数の領域を80%以上の精度で推定できることがわかった。 推定境界を様々なCOPソルバで評価することにより、Bionはいくつかの問題に対する解法を改善するが、近接境界の効果は一般に問題依存である。

関連論文リスト

• 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)
• Online POMDP Planning with Anytime Deterministic Guarantees [11.157761902108692]
  不確実性の下での計画は、部分的に観測可能なマルコフ決定プロセス(POMDP)を用いて数学的に定式化できる POMDPの最適計画を見つけるには計算コストがかかり、小さなタスクにのみ適用可能である。 簡便な解と理論的に最適な解との決定論的関係を導出する。
  論文  参考訳（メタデータ） (2023-10-03T04:40:38Z)
• Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs [5.28005598366543]
  ニューラルダイビング(ND)は、混合プログラム(MIP)における部分的な離散変数代入を生成する学習ベースのアプローチの1つである。 カバー範囲を最適化するためのポストホック法と学習に基づくアプローチを導入する。 実験結果から、ニューラルネットワークを学習して高品質な実現可能なソリューションを見つけるためのカバレッジを推定することで、NeurIPS ML4COデータセットの最先端のパフォーマンスが達成されることが示された。
  論文  参考訳（メタデータ） (2023-08-01T07:03:16Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。 他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。 ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
  論文  参考訳（メタデータ） (2022-07-01T17:58:29Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Predictive Machine Learning of Objective Boundaries for Solving COPs [21.206740640268283]
  CPソルバをサポートするツールとして応用された境界推定フレームワークを提案する。 本枠組みでは, 境界推定に適したMLモデルについて検討し, 評価を行った。 以上の結果から,これらのCOPに対して,最小限のオーバーヘッドで準最適境界を学習できることが示唆された。
  論文  参考訳（メタデータ） (2021-11-04T21:08:07Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• A Discriminative Technique for Multiple-Source Adaptation [55.5865665284915]
  本稿では,マルチソース適応のための新しい識別手法,MSA,問題を提案する。 我々のソリューションは、ソースドメインからのラベルなしデータから容易に正確に推定できる条件付き確率のみを必要とする。 実世界の応用実験により、新しい識別的MSAアルゴリズムは、以前の生成解よりも優れていたことがさらに証明された。
  論文  参考訳（メタデータ） (2020-08-25T14:06:15Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。