論文の概要: SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One
Constraints
- arxiv url: http://arxiv.org/abs/2110.08068v1
- Date: Fri, 15 Oct 2021 12:53:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-18 13:41:26.399933
- Title: SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One
Constraints
- Title（参考訳）: at-most-one制約を伴う疑似boolean制約のためのsat符号化
- Authors: Miquel Bofill and Jordi Coll and Peter Nightingale and Josep Suy and
Felix Ulrich-Oltean and Mateu Villaret
- Abstract要約: Pseudo-Boolean(PB)制約の符号化について検討する。
PB(AMO)エンコーディングは、より多くのインスタンスをタイムリミット内で解決し、時には1桁以上の時間改善を行う。
- 参考スコア（独自算出の注目度）: 5.62245362437303
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: When solving a combinatorial problem using propositional satisfiability
(SAT), the encoding of the problem is of vital importance. We study encodings
of Pseudo-Boolean (PB) constraints, a common type of arithmetic constraint that
appears in a wide variety of combinatorial problems such as timetabling,
scheduling, and resource allocation. In some cases PB constraints occur
together with at-most-one (AMO) constraints over subsets of their variables
(forming PB(AMO) constraints). Recent work has shown that taking account of
AMOs when encoding PB constraints using decision diagrams can produce a
dramatic improvement in solver efficiency. In this paper we extend the approach
to other state-of-the-art encodings of PB constraints, developing several new
encodings for PB(AMO) constraints. Also, we present a more compact and
efficient version of the popular Generalized Totalizer encoding, named Reduced
Generalized Totalizer. This new encoding is also adapted for PB(AMO)
constraints for a further gain. Our experiments show that the encodings of
PB(AMO) constraints can be substantially smaller than those of PB constraints.
PB(AMO) encodings allow many more instances to be solved within a time limit,
and solving time is improved by more than one order of magnitude in some cases.
We also observed that there is no single overall winner among the considered
encodings, but efficiency of each encoding may depend on PB(AMO)
characteristics such as the magnitude of coefficient values.
- Abstract（参考訳）: 命題満足度(SAT)を用いて組合せ問題を解く場合、問題の符号化は極めて重要である。
Pseudo-Boolean(PB)制約の符号化について検討する。これは、時間、スケジューリング、リソース割り当てなど、様々な組み合わせ問題に現れる一般的なタイプの算術制約である。
PB制約は、変数のサブセット(PB(AMO)制約を形成する)に対する at-most-one (AMO) 制約と共に発生する。
近年の研究では、決定図を用いたPB制約の符号化におけるAMOの活用により、解法効率が劇的に向上することが示されている。
本稿では,本手法をpb制約の最先端エンコーディングに拡張し,pb(amo)制約のための新たなエンコーディングを複数開発する。
また,一般的な一般化総和符号のよりコンパクトで効率的なバージョンであるreduced general totalizerを提案する。
この新たなエンコーディングはPB(AMO)制約にも適用され、さらなる利得が得られる。
実験の結果,PB(AMO)制約の符号化は,PB制約の符号化よりもかなり小さいことがわかった。
pb(amo)エンコーディングは、多くのインスタンスをタイムリミット内で解決することを可能にし、場合によっては1桁以上のマグニチュードで解決する。
また, 検討したエンコーディングのうち, 全体の勝者はひとつも存在しないが, 各エンコーディングの効率は係数値の大きさなどのpb(amo)特性に依存する可能性がある。
関連論文リスト
- Deep Learning Assisted Multiuser MIMO Load Modulated Systems for
Enhanced Downlink mmWave Communications [68.96633803796003]
本稿では, マルチユーザ負荷変調アレイ (MU-LMA) に着目し, マイクロウェーブ (mmWave) マルチインプット・マルチアウトプット (MIMO) システムにおいて, マルチユーザ負荷変調アレイ (MU-LMA) の小型化とコスト削減を図っている。
ダウンリンクMU-LMAの既存のプリコーディングアルゴリズムは、自由度と複雑なシステム構成の低下に悩まされるサブアレイ構造化(SAS)送信機に依存している。
本稿では,FAS (Full-array Structured) 送信機を用いたMU-LMAシステムを提案し,それに応じて2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-08T08:54:56Z) - Using Integer Constraint Solving in Reuse Based Requirements Engineering [0.0]
製品ライン(PL)は、再利用ベースの構成に対する効果的なアプローチを証明した。
現在、製品は制約満足度問題と見なせることが広く認識されている。
制約プログラミングをPLの制約を指定するための第一選択候補として考えるのは当然である。
本稿では,PL制約の指定に整数制約プログラミングを用いることについて,さらに検討する。
論文 参考訳（メタデータ） (2023-09-28T09:20:07Z) - Toward Unified Controllable Text Generation via Regular Expression
Instruction [56.68753672187368]
本稿では,正規表現の利点をフル活用し,多様な制約を一様にモデル化する命令ベース機構を用いた正規表現指導(REI)を提案する。
提案手法では,中規模言語モデルの微調整や,大規模言語モデルでの少数ショット・インコンテクスト学習のみを要し,各種制約の組み合わせに適用した場合のさらなる調整は不要である。
論文 参考訳（メタデータ） (2023-09-19T09:05:14Z) - Learning to Select SAT Encodings for Pseudo-Boolean and Linear Integer
Constraints [1.1371889042789218]
本稿では,制約問題に対する標準的な特徴セットを用いて,効率よく符号化を選択することができることを示す。
擬似ブール制約と線形制約に特化して設計された,新しい機能セットにより,性能が向上する。
結果は、同じ機能セットを使用する場合、AutoFolioと良好に比較されます。
論文 参考訳（メタデータ） (2023-07-18T15:26:46Z) - DiNADO: Norm-Disentangled Neurally-Decomposed Oracles for Controlling Language Models [55.06442277395388]
NeurAlly-Decomposed Oracle (NADO)は、大きな言語モデルで制御可能な生成のための強力なアプローチである。
バニラNADOは低確率制御信号の減衰勾配に悩まされる。
本稿では,NADOアルゴリズムの性能向上を図るために,NADOアルゴリズムの改良版であるDiNADOを提案する。
論文 参考訳（メタデータ） (2023-06-20T18:36:52Z) - Qubit Number Optimization for Restriction Terms of QUBO Hamiltonians [62.997667081978825]
数学的には$R$の分数値を求めることができる。
制限ハミルトニアンの実装に必要な量子ビット数をさらに減らす方法を示す。
最後に、FRCの実装に直面した場合、DWaveのAdvantage$_$system4.1 Quantum Annealer(QA)の応答を特徴付ける。
論文 参考訳（メタデータ） (2023-06-12T08:25:56Z) - Solving Quantum-Inspired Perfect Matching Problems via Tutte's
Theorem-Based Hybrid Boolean Constraints [39.96302127802424]
量子コンピューティングで発生するハイブリッドブール制約の新しい応用について検討する。
この問題は、エッジカラーグラフにおける制約付き完全マッチングに関連している。
本稿では,ハイブリッド制約による制約マッチング問題の直接符号化が不十分であり,特殊な手法が依然として必要であることを示す。
論文 参考訳（メタデータ） (2023-01-24T06:14:24Z) - 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) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Encoding Linear Constraints into SAT [0.0]
複数値決定ダイアグラムとソートネットワークに基づく新しいSATエンコーディングを定義する。
線形整数解法 (MIP) よりも優れており, 適切な問題に対して LCG や SMT より優れている場合もある。
論文 参考訳（メタデータ） (2020-05-05T11:37:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。