論文の概要: SAT Encoding for Set of At-Most-K Cardinality Constraints with Ladder Shape
- arxiv url: http://arxiv.org/abs/2611.04637v1
- Date: Tue, 03 Nov 2026 10:27:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-09 14:21:59.177293
- Title: SAT Encoding for Set of At-Most-K Cardinality Constraints with Ladder Shape
- Title(参考訳): ラダー形状をもつat-Most-K心磁図のSAT符号化
- Abstract要約: 本稿では,ラダーAMK制約(Ladder AMK)と呼ばれるラダー構造に配置されたAtMost-K濃度制約の列を表現するために設計された新しいSAT符号を提案する。
提案した符号化法は,まずAMK制約のシーケンスを分割ブロックに分解し,各ブロックを個別に符号化するのではなく全体として符号化する。
この手法は、SATソルバにおける制約解の効率を向上し、エンコーディングのサイズ、変数の数、生成節を著しく削減する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper presents a novel SAT encoding designed to represent a sequence of At-Most-K cardinality constraints arranged in a ladder-like structure, referred to as the Ladder AMK constraint. These AMK constraints feature a ladder-like arrangement, with shared common variables in the center and two variables differing at the beginning and the end. The proposed encoding first decomposes the sequence of AMK constraints into separated blocks, then encodes each block as a whole rather than encoding each AMK constraint individually. This approach improves the efficiency of constraint solving in SAT solvers by significantly reducing the size of the encoding, precisely the number of variables, and the generated clauses required. To achieve this, the encoding employs Sequential Counter to encode each block and constructs clauses that link adjacent blocks, ensuring equivalence with the input constraints. Compared to the previously proposed encoding that uses BDD for Ladder AMO constraint, our encoding requires fewer variables and clauses. Our study is the first study that develops SAT encoding for Ladder AMK constraints with k>1. Experimental results on single Ladder AMO and Ladder AMK constraints indicate that our encoding significantly enhances both the size of the encoding and the efficiency of solving time compared to existing encodings. Furthermore, by evaluating on the two real-world combinatorial problems, namely Anti-bandwidth Problem and Nurse Rostering Problem, we found that the proposed encoding surpasses alternative encodings, as well as more advanced Constraint Programming and Mixed Integer Programming solvers. In summary, the SAT encoding technique presented in this paper provides a more efficient method for encoding sequence constraint, specifically Ladder AMK constraint, which could enhance the effectiveness of SAT solving for various problems involving this type of constraint.
- Abstract(参考訳): 本稿では,ラダーAMK制約(Ladder AMK)と呼ばれるラダー構造に配置されたAt-Most-K濃度制約の列を表現するために設計された新しいSAT符号を提案する。
これらのAMK制約ははしごのような配置を特徴とし、中央に共通変数が共有され、先頭と端に2つの変数が異なる。
提案した符号化法は,まずAMK制約のシーケンスを分割ブロックに分解し,各ブロックを個別に符号化するのではなく全体として符号化する。
この手法は、SATソルバにおける制約解の効率を向上し、エンコーディングのサイズ、変数の数、生成節を著しく削減する。
これを実現するために、エンコーディングではSequential Counterを使用して各ブロックをエンコードし、隣接するブロックをリンクする節を構築し、入力制約と等価性を確保する。
Ladder AMO制約にBDDを使用した以前に提案されたエンコーディングと比較して、私たちのエンコーディングは変数や節が少なくなります。
本研究は, k>1のラダーAMK制約に対するSAT符号化を開発した最初の研究である。
単一のLadder AMOとLadder AMKの制約による実験結果から,既存の符号化に比べて符号化のサイズと解時間効率が著しく向上することが示唆された。
さらに,反帯域問題とNurse Rostering問題という2つの実世界の組合せ問題を評価することにより,提案手法が代替エンコーディングを超越し,より高度な制約プログラミングと混合整数プログラミングの解法が得られた。
要約して,本論文で提案するSAT符号化技術は,シーケンス制約,特にLadder AMK制約をより効率的に符号化する方法を提供する。
関連論文リスト
- Identifying Good Rules for Efficient SAT Encodings of Single-Constant Multiplication Using Machine Learning [0.0]
本稿では,SCM SAT符号化を高速化するニューロシンボリックフレームワークを提案する。
未確認17-32ビット定数実験の結果,符号化時間では1~2桁,メモリ使用量では97%以上,分枝数では1~2桁,分枝数では97%以上であった。
論文 参考訳(メタデータ) (2026-07-23T11:15:55Z) - Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS [0.47267770920095525]
制約付きシンドロームデコーディングの解法は、特定の構造のベクトルと、新たに構築された符号の小さなノルムから導出可能であることを示す。
これにより、リミテッドシンドロームデコーディングをコードベース(レギュラーシンドロームデコーディング)と格子ベース問題の両方に削減できる。
論文 参考訳(メタデータ) (2026-04-10T13:03:00Z) - Fast correlated decoding of transversal logical algorithms [67.01652927671279]
大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。
近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。
ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
論文 参考訳(メタデータ) (2025-05-19T18:00:00Z) - Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
トークンの制約を評価するのは 違法にコストがかかる
LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。
我々のアプローチは最先端のベースラインよりも優れていることを示す。
論文 参考訳(メタデータ) (2025-04-07T18:30:18Z) - Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。
本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
論文 参考訳(メタデータ) (2024-01-30T11:40:24Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。
RM符号は制限されたレートのみを許容する。
効率的なデコーダは、RM符号に対して有限長で利用可能である。
論文 参考訳(メタデータ) (2023-01-16T04:11:14Z) - SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One
Constraints [5.62245362437303]
Pseudo-Boolean(PB)制約の符号化について検討する。
PB(AMO)エンコーディングは、より多くのインスタンスをタイムリミット内で解決し、時には1桁以上の時間改善を行う。
論文 参考訳(メタデータ) (2021-10-15T12:53:01Z) - Yet Another Comparison of SAT Encodings for the At-Most-K Constraint [0.0]
本稿では,最大k制約に対するバイナリアダプタ符号化の性能について述べる。
以前の実験では、k$>1のシーケンシャルカウンタエンコーディングの競合性を示しており、並列カウンタエンコーディングを除外している。
論文 参考訳(メタデータ) (2020-05-12T03:23:00Z) - Encoding Linear Constraints into SAT [0.0]
複数値決定ダイアグラムとソートネットワークに基づく新しいSATエンコーディングを定義する。
線形整数解法 (MIP) よりも優れており, 適切な問題に対して LCG や SMT より優れている場合もある。
論文 参考訳(メタデータ) (2020-05-05T11:37:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。