論文の概要: The Complexity of Symmetry Breaking Beyond Lex-Leader
- arxiv url: http://arxiv.org/abs/2407.04419v1
- Date: Fri, 5 Jul 2024 11:09:55 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-08 13:50:07.532413
- Title: The Complexity of Symmetry Breaking Beyond Lex-Leader
- Title（参考訳）: Lex-Leaderを超える対称性の複雑さ
- Authors: Markus Anders, Sofia Brenner, Gaurav Rattan,
- Abstract要約: 本稿では,SAT における完全 SBP や lex-leader などの計算の複雑さについて検討する。
本研究の主な成果は,SBPを効率よく計算する上での自然な障壁,すなわちグラフ非同型性の効率的な証明である。
この結果から,行列対称性を持つ行列モデルやグラフ生成問題などの重要なCP問題に対して,短いSBPを得ることの難しさが説明できる。
- 参考スコア（独自算出の注目度）: 2.8733698089003745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Symmetry breaking is a widely popular approach to enhance solvers in constraint programming, such as those for SAT or MIP. Symmetry breaking predicates (SBPs) typically impose an order on variables and single out the lexicographic leader (lex-leader) in each orbit of assignments. Although it is NP-hard to find complete lex-leader SBPs, incomplete lex-leader SBPs are widely used in practice. In this paper, we investigate the complexity of computing complete SBPs, lex-leader or otherwise, for SAT. Our main result proves a natural barrier for efficiently computing SBPs: efficient certification of graph non-isomorphism. Our results explain the difficulty of obtaining short SBPs for important CP problems, such as matrix-models with row-column symmetries and graph generation problems. Our results hold even when SBPs are allowed to introduce additional variables. We show polynomial upper bounds for breaking certain symmetry groups, namely automorphism groups of trees and wreath products of groups with efficient SBPs.
- Abstract（参考訳）: 対称性の破れは、SATやMIPのような制約プログラミングにおける問題解決者を強化するために広く使われているアプローチである。
対称性の破れ述語(SBP)は、通常、変数に順序を課し、各割り当ての軌道にレキソグラフィーリーダー(レックスリーダー)を選別する。
完全なレックスリーダーSBPを見つけることはNPハードであるが、実際には不完全なレックスリーダーSBPが広く用いられている。
本稿では,SAT における完全 SBP や lex-leader などの計算の複雑さについて検討する。
本研究の主な成果は,SBPを効率よく計算する上での自然な障壁,すなわちグラフ非同型性の効率的な証明である。
この結果から,行列対称性を持つ行列モデルやグラフ生成問題などの重要なCP問題に対して,短いSBPを得ることの難しさが説明できる。
我々の結果は、SBPが追加変数を導入することを許されたとしても保たれる。
我々は、ある対称性群、すなわち木の自己同型群と効率的なSBPを持つ群のリース積を破るための多項式上界を示す。
関連論文リスト
- Scalable unsupervised alignment of general metric and non-metric structures [21.29255788365408]
異なるドメインからのデータのアライメントは、非常に異なる領域にわたる幅広いアプリケーションによる機械学習の基本的な問題である。
我々は、2次代入問題 (QAP) の最小化問題でもある、関連よく計算可能な線形代入問題 (LAP) を学習する。
単一セルマルチオミクスとニューラル潜在空間からの合成および実データに対するアプローチを評価する。
論文 参考訳（メタデータ） (2024-06-19T12:54:03Z) - Learning Broadcast Protocols [1.9336815376402723]
任意の数のプロセスで分散システムを学習する問題に初めて注目する。
細かな放送プロトコルを考えると、これらは有限カットオフと隠蔽状態のない放送プロトコルである。
試料が十分に完全であれば、微細なBPと一致する試料から正しいBPを推測し、最小の等価BPを推定できる学習アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-06-25T16:26:48Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - Multilayer hypergraph clustering using the aggregate similarity matrix [0.7373617024876725]
ハイパーグラフブロックモデル(HSBM)の多層版におけるコミュニティリカバリ問題について考察する。
本研究では、半定値プログラミング(SDP)アプローチを調査し、正確な回復を保証するモデルパラメータに関する情報理論条件を求める。
論文 参考訳（メタデータ） (2023-01-27T11:15:46Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
我々は、Symmetry Breaking Constraintsを解釈可能な一階制約の集合に引き上げる、Answer Set Programmingのための新しいモデル指向のアプローチを導入する。
実験は、我々のフレームワークがインスタンス固有のSBCから一般的な制約を学習できることを実証する。
論文 参考訳（メタデータ） (2021-12-22T11:27:48Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳（メタデータ） (2020-06-22T17:58:54Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である
本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。
また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文 参考訳（メタデータ） (2020-01-13T13:16:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。