論文の概要: Automatic Generation of Polynomial Symmetry Breaking Constraints

• arxiv url: http://arxiv.org/abs/2602.08297v1
• Date: Mon, 09 Feb 2026 06:05:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:25.081992
• Title: Automatic Generation of Polynomial Symmetry Breaking Constraints
• Title（参考訳）: 多項式対称性破断制約の自動生成
• Authors: Madalina Erascu, Johannes Middeke,
• Abstract要約: 対称性ブレーカーとして使用できる不等式列をランダムに生成する手法を提案する。 この方法は任意の基底と整数プログラムに固有の記号置換のグループを入力として要求する。 単純な対称性ブレーカー、特に少数の変数と置換を組み合わせることで、作業時間を大幅に短縮することが判明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Symmetry in integer programming causes redundant search and is often handled with symmetry breaking constraints that remove as many equivalent solutions as possible. We propose an algebraic method which allows to generate a random family of polynomial inequalities which can be used as symmetry breakers. The method requires as input an arbitrary base polynomial and a group of permutations which is specific to the integer program. The computations can be easily carried out in any major symbolic computation software. In order to test our approach, we describe a case study on near half-capacity 0-1 bin packing instances which exhibit substantial symmetries. We statically generate random quadratic breakers and add them to a baseline integer programming problem which we then solve with Gurobi. It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.
• Abstract（参考訳）: 整数プログラミングにおける対称性は冗長な探索を引き起こし、しばしば可能な限り多くの等価解を除去する対称性を破る制約で扱われる。 対称性ブレーカーとして使用できる多項式の不等式をランダムに生成できる代数的手法を提案する。 この方法は任意の基底多項式と整数プログラムに固有の置換のグループを入力として要求する。 計算は、どんな主要な記号計算ソフトウェアでも容易に行うことができる。 提案手法を試すために, かなりの対称性を示すほぼ半容量の0-1ビンパッキングインスタンスのケーススタディについて述べる。 ランダムな2次ブレーカを静的に生成し、それらをベースライン整数プログラミング問題に追加し、グロビで解いた。 単純な対称性ブレーカー、特に少数の変数と置換を組み合わせることで、作業時間を大幅に短縮することが判明した。

関連論文リスト

• Faster Symmetry Breaking Constraints for Abstract Structures [1.784933900656067]
  それらの表現をよりうまく活用することで抽象構造の対称性を破る新しい不完全な方法を示す。 本手法は、一般的に発生する対称性の一種である、識別不能な物体から生じる対称性を破ることに適用する。
  論文  参考訳（メタデータ） (2025-11-14T07:34:23Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Linear programming with unitary-equivariant constraints [2.0305676256390934]
  ユニタリ同値(英: Unitary equivariance)は、物理学や数学において多くの文脈で発生する自然な対称性である。 追加の対称性の仮定の下では、この問題は、$d$でスケールしない時間で解決できる線形プログラムに還元されることを示す。 また,本手法を一般ユニタリ同変半定プログラムに拡張する可能性についても概説する。
  論文  参考訳（メタデータ） (2022-07-12T17:37:04Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。 確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。 例として、正則および準正則なクォービット状態集合の推理を計算する。
  論文  参考訳（メタデータ） (2021-12-03T01:24:57Z)

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

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