論文の概要: Faster Symmetry Breaking Constraints for Abstract Structures

• arxiv url: http://arxiv.org/abs/2511.11029v1
• Date: Fri, 14 Nov 2025 07:34:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.477333
• Title: Faster Symmetry Breaking Constraints for Abstract Structures
• Title（参考訳）: 抽象構造に対する高速な対称性破砕法
• Authors: Özgür Akgün, Mun See Chang, Ian P. Gent, Christopher Jefferson,
• Abstract要約: それらの表現をよりうまく活用することで抽象構造の対称性を破る新しい不完全な方法を示す。 本手法は、一般的に発生する対称性の一種である、識別不能な物体から生じる対称性を破ることに適用する。
• 参考スコア（独自算出の注目度）: 1.784933900656067
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In constraint programming and related paradigms, a modeller specifies their problem in a modelling language for a solver to search and return its solution(s). Using high-level modelling languages such as Essence, a modeller may express their problems in terms of abstract structures. These are structures not natively supported by the solvers, and so they have to be transformed into or represented as other structures before solving. For example, nested sets are abstract structures, and they can be represented as matrices in constraint solvers. Many problems contain symmetries and one very common and highly successful technique used in constraint programming is to "break" symmetries, to avoid searching for symmetric solutions. This can speed up the solving process by many orders of magnitude. Most of these symmetry-breaking techniques involve placing some kind of ordering for the variables of the problem, and picking a particular member under the symmetries, usually the smallest. Unfortunately, applying this technique to abstract variables produces a very large number of complex constraints that perform poorly in practice. In this paper, we demonstrate a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations. We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry, and show that our method is faster than the previous methods proposed in (Akgün et al. 2025).
• Abstract（参考訳）: 制約プログラミングおよび関連するパラダイムにおいて、モデラーは、解法が解を探索して返却するためのモデリング言語で問題を特定する。 Essenceのようなハイレベルなモデリング言語を使用することで、モデラーは抽象構造の観点から問題を表現できる。 これらは、ソルバがネイティブにサポートしていない構造なので、解決する前に他の構造に変換または表現する必要がある。 例えば、ネスト集合は抽象構造であり、制約解の行列として表すことができる。 多くの問題には対称性が含まれており、制約プログラミングで使われる非常に一般的で高度に成功した技法は対称解の探索を避けるために対称性を「破る」ことである。 これにより、解決プロセスを桁違いにスピードアップすることができる。 これらの対称性を破る技法のほとんどは、問題の変数を何らかの順序付けし、対称性の下にある特定の部材(通常は最小)を選ぶことである。 残念なことに、この手法を抽象変数に適用すると、実際にはあまり機能しない非常に多くの複雑な制約が生じる。 本稿では,それらの表現をよりよく活用することで,抽象構造の対称性を破る新しい不完全な方法を示す。 本手法は,従来提案されていた手法よりも高速であることを示す(Akgün et al 2025)。

関連論文リスト

• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  CoT(Chain-of-Thought)は、問題を逐次ステップに分解することで、大きな言語モデル(LLM)の推論を促進する。 思考のシジー(Syzygy of Thoughts, SoT)は,CoTを補助的,相互関連的な推論経路を導入して拡張する新しいフレームワークである。 SoTはより深い論理的依存関係をキャプチャし、より堅牢で構造化された問題解決を可能にする。
  論文  参考訳（メタデータ） (2025-04-13T13:35:41Z)
• Exploiting Symmetries in MUS Computation (Extended version) [11.266189935383476]
  eXplainable Constraint Solving (XCS) では、満足できない制約の集合から最小不満足な部分集合(MUS)を抽出することが一般的である。 MUSの発見は、高度に対称的な問題に対して計算コストがかかる。 本稿では、既存の対称性処理技術からインスピレーションを得て、よく知られたMUS計算手法を適用して仕様の対称性を利用する。
  論文  参考訳（メタデータ） (2024-12-18T08:34:32Z)
• Equivariant Symmetry Breaking Sets [0.6475999521931204]
  等価ニューラルネットワーク(ENN)は、基礎となる対称性を含むアプリケーションに非常に効果的であることが示されている。 完全同変で、自発対称性の破れに対処する最初のフレームワークである新しい対称性破れフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-02-05T02:35:11Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。 凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。 切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
  論文  参考訳（メタデータ） (2023-03-28T01:30:40Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。 これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。 制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
  論文  参考訳（メタデータ） (2022-08-23T18:56:05Z)
• A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming [0.0]
  我々は,小問題インスタンスのSBCを解釈可能な一階制約の集合に引き上げる,新しいモデル指向アンサーセットプログラミングを導入する。 簡単な問題をターゲットにして,先進的な意思決定問題にも適用できるように拡張することを目指している。
  論文  参考訳（メタデータ） (2022-08-05T10:50:03Z)
• Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation [88.14365009076907]
  反復的洗練は表現学習に有用なパラダイムである。 トレーニングの安定性とトラクタビリティを向上させる暗黙の差別化アプローチを開発する。
  論文  参考訳（メタデータ） (2022-07-02T10:00:35Z)
• SPANet: Generalized Permutationless Set Assignment for Particle Physics using Symmetry Preserving Attention [62.43586180025247]
  大型ハドロン衝突型加速器の衝突は、観測された粒子の可変サイズの集合を生成する。 崩壊生成物の物理対称性は、観測された粒子の崩壊生成物の割り当てを複雑にする。 本稿では,対称性を保った注目ネットワークを構築するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-07T18:18:20Z)

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

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