論文の概要: Solution Enumeration by Optimality in Answer Set Programming

• arxiv url: http://arxiv.org/abs/2108.03474v1
• Date: Sat, 7 Aug 2021 15:50:23 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-10 15:10:03.771225
• Title: Solution Enumeration by Optimality in Answer Set Programming
• Title（参考訳）: 解集合プログラミングにおける最適性による解列挙
• Authors: Jukka Pajunen, Tomi Janhunen
• Abstract要約: この研究は最適解の素列挙を超えて、最適性による解列挙の計算タスクに対処する(SEO)。 既存の解解法は、既に全ての(最適)解集合の列挙をサポートしている。 上述した解集合列挙のタスクに対する最初の一般アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.122161391301866
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Given a combinatorial search problem, it may be highly useful to enumerate its (all) solutions besides just finding one solution, or showing that none exists. The same can be stated about optimal solutions if an objective function is provided. This work goes beyond the bare enumeration of optimal solutions and addresses the computational task of solution enumeration by optimality (SEO). This task is studied in the context of Answer Set Programming (ASP) where (optimal) solutions of a problem are captured with the answer sets of a logic program encoding the problem. Existing answer-set solvers already support the enumeration of all (optimal) answer sets. However, in this work, we generalize the enumeration of optimal answer sets beyond strictly optimal ones, giving rise to the idea of answer set enumeration in the order of optimality (ASEO). This approach is applicable up to the best k answer sets or in an unlimited setting, which amounts to a process of sorting answer sets based on the objective function. As the main contribution of this work, we present the first general algorithms for the aforementioned tasks of answer set enumeration. Moreover, we illustrate the potential use cases of ASEO. First, we study how efficiently access to the next-best solutions can be achieved in a number of optimization problems that have been formalized and solved in ASP. Second, we show that ASEO provides us with an effective sampling technique for Bayesian networks.
• Abstract（参考訳）: 組合せ探索問題を考えると、一つの解を見つけるだけでなく(すべて)その解を列挙したり、存在しないことを示すのに非常に有用である。 目的関数が与えられた場合、最適解についても同様に述べることができる。 この仕事は最適解の素数列挙を超越しており、最適性による解の列挙(seo)の計算タスクに対処する。 このタスクは Answer Set Programming (ASP) の文脈で研究され、問題の(最適)解は問題を符号化する論理プログラムの解集合でキャプチャされる。 既存の解解法は、既に全ての(最適)解集合の列挙をサポートしている。 しかし,本研究では,最適解集合の列挙を厳密な最適解集合を超えて一般化し,最適解集合の列挙を最適性(ASEO)の順に導く。 このアプローチは、最高の k 個の解集合または無限の設定に適用できるが、これは目的関数に基づいて解集合をソートする過程に相当する。 本研究の主な貢献として,上記の解集合列挙のタスクに対して,最初の一般アルゴリズムを提案する。 さらに,ASEOの潜在的なユースケースについて述べる。 まず、asp.netで形式化され解決された多くの最適化問題において、次善のソリューションにいかに効率的にアクセスできるかについて検討する。 次に,ASEOがベイジアンネットワークに有効なサンプリング手法を提供することを示す。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem [2.9730678241643815]
  教師付き機械学習に基づく予測解法選択手法を提案する。 70%以上の場合において、最良の解法が選択され、約90%の場合には、上位2の解法が選択される。 この探索は、量子ソルバ選択における機械学習の可能性を証明し、その自動化の基礎を定めている。
  論文  参考訳（メタデータ） (2024-08-07T08:14:58Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• RIGA: A Regret-Based Interactive Genetic Algorithm [14.388696798649658]
  そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。 我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。 いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
  論文  参考訳（メタデータ） (2023-11-10T13:56:15Z)
• Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling [2.370481325034443]
  Answer Set Programming (ASP)では、ユーザーは宣言的に問題を定義でき、効率的な解法でそれを解決できる。 他の研究領域では、論理ベースのベンダー分解(LBBD)が有効であることが証明された。 本稿では, 医療分野の応用を事例として, LBBD を ASP に適用する。
  論文  参考訳（メタデータ） (2023-05-19T19:34:47Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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