論文の概要: Efficient lifting of symmetry breaking constraints for complex combinatorial problems

• arxiv url: http://arxiv.org/abs/2205.07129v1
• Date: Sat, 14 May 2022 20:42:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 16:46:33.142377
• Title: Efficient lifting of symmetry breaking constraints for complex combinatorial problems
• Title（参考訳）: 複素組合せ問題に対する対称性破断制約の効率的な持ち上げ
• Authors: Alice Tarzariol and Martin Gebser and Mark Law and Konstantin Schekotihin
• Abstract要約: この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。 Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
• 参考スコア（独自算出の注目度）: 9.156939957189502
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many industrial applications require finding solutions to challenging combinatorial problems. Efficient elimination of symmetric solution candidates is one of the key enablers for high-performance solving. However, existing model-based approaches for symmetry breaking are limited to problems for which a set of representative and easily-solvable instances is available, which is often not the case in practical applications. This work extends the learning framework and implementation of a model-based approach for Answer Set Programming to overcome these limitations and address challenging problems, such as the Partner Units Problem. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP, redefine the learning task, and suggest a new example generation method to scale up the approach. The experiments conducted for different kinds of Partner Units Problem instances demonstrate the applicability of our approach and the computational benefits due to the first-order constraints learned.
• Abstract（参考訳）: 多くの産業応用は組合せ問題に対する解決策を見つける必要がある。 対称解候補の効率的な除去は、高性能解法の主要な実現要因の1つである。 しかし、対称性の破れに対する既存のモデルベースのアプローチは、代表的かつ容易に解くことができるインスタンスの集合が利用可能である問題に限定されている。 この作業は、Answer Set Programmingの学習フレームワークとモデルベースのアプローチの実装を拡張して、これらの制限を克服し、パートナーユニット問題のような課題に対処します。 特に,インダクティブ論理プログラミングシステムilaspに新しいコンフリクト解析アルゴリズムを組み込んで学習タスクを再定義し,そのアプローチをスケールアップするための新しいサンプル生成手法を提案する。 パートナーユニットの異なる種類の問題インスタンスに対して実施した実験は,我々のアプローチの適用可能性と,学習した一階制約による計算上のメリットを示している。

関連論文リスト

• Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
  テンプレート設計問題(TDP)は、多くの対称性を持つ難しい問題であり、それをより複雑にしている。 本稿では,テンプレート設計の適合性を評価することを目的として,多種多様なメタヒューリスティクスを探索し,解析する。
  論文  参考訳（メタデータ） (2024-11-05T06:29:12Z)
• IC/DC: Surpassing Heuristic Solvers in Combinatorial Optimization with Diffusion Models [6.260482448679642]
  IC/DCは,教師なしの学習型最適化フレームワークである。 IC/DCは2つの異なる項目を含む問題の解決に特化しており、有効な解を生成するのに問題固有の探索プロセスは必要ない。 私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。
  論文  参考訳（メタデータ） (2024-10-15T06:53:30Z)
• 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)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。 TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。 TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
  論文  参考訳（メタデータ） (2023-10-06T01:40:09Z)
• Conjunctive Query Based Constraint Solving For Feature Model Configuration [79.14348940034351]
  本稿では、制約満足度問題を解決するために共役クエリーを適用する方法を示す。 このアプローチは、構成タスクを解決するために、広範囲のデータベース技術の応用を可能にする。
  論文  参考訳（メタデータ） (2023-04-26T10:08:07Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming [0.0]
  我々は,小問題インスタンスのSBCを解釈可能な一階制約の集合に引き上げる,新しいモデル指向アンサーセットプログラミングを導入する。 簡単な問題をターゲットにして,先進的な意思決定問題にも適用できるように拡張することを目指している。
  論文  参考訳（メタデータ） (2022-08-05T10:50:03Z)
• Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach [0.0]
  本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。 環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
  論文  参考訳（メタデータ） (2022-05-10T15:54:06Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。 実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
  論文  参考訳（メタデータ） (2021-12-22T11:27:48Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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