論文の概要: Lifting Symmetry Breaking Constraints with Inductive Logic Programming
- arxiv url: http://arxiv.org/abs/2112.11806v1
- Date: Wed, 22 Dec 2021 11:27:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-23 15:10:18.750164
- Title: Lifting Symmetry Breaking Constraints with Inductive Logic Programming
- Title（参考訳）: 帰納的論理プログラミングによるリフティング対称性の破れ
- Authors: Alice Tarzariol, Martin Gebser, Konstantin Schekotihin
- Abstract要約: 我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。
実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
- 参考スコア（独自算出の注目度）: 2.036811219647753
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Efficient omission of symmetric solution candidates is essential for
combinatorial problem-solving. Most of the existing approaches are
instance-specific and focus on the automatic computation of Symmetry Breaking
Constraints (SBCs) for each given problem instance. However, the application of
such approaches to large-scale instances or advanced problem encodings might be
problematic since the computed SBCs are propositional and, therefore, can
neither be meaningfully interpreted nor transferred to other instances. As a
result, a time-consuming recomputation of SBCs must be done before every
invocation of a solver.
To overcome these limitations, we introduce a new model-oriented approach for
Answer Set Programming that lifts the SBCs of small problem instances into a
set of interpretable first-order constraints using the Inductive Logic
Programming paradigm. Experiments demonstrate the ability of our framework to
learn general constraints from instance-specific SBCs for a collection of
combinatorial problems. The obtained results indicate that our approach
significantly outperforms a state-of-the-art instance-specific method as well
as the direct application of a solver.
- Abstract（参考訳）: 対称解候補の効率的な脱落は組合せ問題解決に不可欠である。
既存のアプローチのほとんどはインスタンス固有であり、各問題インスタンスに対してSBC(Symmetry Breaking Constraints)の自動計算に重点を置いている。
しかしながら、計算されたsbcは命題的であるため、大規模インスタンスや高度な問題エンコーディングへのそのようなアプローチの適用は問題となりうるため、意味のある解釈も他のインスタンスへの転送もできない。
その結果、SBCの計算に要する時間は、ソルバの呼び出しに先立って行う必要がある。
これらの制約を克服するために、我々は、小さな問題インスタンスのSBCをインダクティブ論理プログラミングパラダイムを用いて解釈可能な一階制約のセットに引き上げるAnswer Set Programmingの新しいモデル指向のアプローチを導入する。
実験では,組換え問題の集合に対して,インスタンス固有のSBCから一般制約を学習する能力を示す。
その結果,提案手法は,解法の直接的適用と同様に,最先端のインスタンス固有メソッドを大幅に上回ることがわかった。
関連論文リスト
- 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) - 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) - Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。
KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。
2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
論文 参考訳（メタデータ） (2022-05-16T08:10:40Z) - Efficient lifting of symmetry breaking constraints for complex
combinatorial problems [9.156939957189502]
この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。
Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
論文 参考訳（メタデータ） (2022-05-14T20:42:13Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver
Surrogates [14.905085636501438]
問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。
このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。
qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
論文 参考訳（メタデータ） (2021-03-19T09:06:12Z) - An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
過制約問題における最小限の障害制約を識別する分割・分散型診断アルゴリズム(FastDiag)を提案する。
ヒットセットの競合指向計算とfastdiagを比較し,詳細な性能解析を行う。
論文 参考訳（メタデータ） (2021-02-17T19:55:42Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。