論文の概要: Learning to Select SAT Encodings for Pseudo-Boolean and Linear Integer Constraints

• arxiv url: http://arxiv.org/abs/2307.09342v2
• Date: Wed, 8 Nov 2023 10:33:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-09 19:23:42.891236
• Title: Learning to Select SAT Encodings for Pseudo-Boolean and Linear Integer Constraints
• Title（参考訳）: Pseudo-Boolean および Linear Integer 制約に対するSAT符号化の学習
• Authors: Felix Ulrich-Oltean, Peter Nightingale, James Alfred Walker
• Abstract要約: 本稿では,制約問題に対する標準的な特徴セットを用いて,効率よく符号化を選択することができることを示す。 擬似ブール制約と線形制約に特化して設計された,新しい機能セットにより,性能が向上する。 結果は、同じ機能セットを使用する場合、AutoFolioと良好に比較されます。
• 参考スコア（独自算出の注目度）: 1.1371889042789218
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many constraint satisfaction and optimisation problems can be solved effectively by encoding them as instances of the Boolean Satisfiability problem (SAT). However, even the simplest types of constraints have many encodings in the literature with widely varying performance, and the problem of selecting suitable encodings for a given problem instance is not trivial. We explore the problem of selecting encodings for pseudo-Boolean and linear constraints using a supervised machine learning approach. We show that it is possible to select encodings effectively using a standard set of features for constraint problems; however we obtain better performance with a new set of features specifically designed for the pseudo-Boolean and linear constraints. In fact, we achieve good results when selecting encodings for unseen problem classes. Our results compare favourably to AutoFolio when using the same feature set. We discuss the relative importance of instance features to the task of selecting the best encodings, and compare several variations of the machine learning method.
• Abstract（参考訳）: 多くの制約満足度と最適化問題は、Boolean Satisfiability problem (SAT) のインスタンスとしてエンコードすることで効果的に解決できる。 しかし、最も単純なタイプの制約でさえ、幅広い性能を持つ文献において多くのエンコーディングを持ち、与えられた問題インスタンスに対して適切なエンコーディングを選択する問題は簡単ではない。 本稿では,教師付き機械学習手法を用いて疑似booleanおよび線形制約に対する符号化選択の問題を検討する。 制約問題に対する標準的特徴集合を用いて符号化を効果的に選択することは可能であるが、擬似ボアおよび線形制約用に特別に設計された新しい特徴集合によりより良い性能が得られることを示す。 実際、見当たらない問題クラスのエンコーディングを選択すると良い結果が得られる。 結果は、同じ機能セットを使用する場合、AutoFolioと良好に比較されます。 最適なエンコーディングを選択するタスクに対するインスタンスの特徴の相対的重要性を論じ、機械学習手法のいくつかのバリエーションを比較した。

関連論文リスト

• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms [0.0]
  本研究では,トラベリングセールスマン問題に対する様々なエンコーディングについて検討する。 置換符号化は、実現可能性の問題に悩まされないため、良好な結果が得られるという証拠が得られます。
  論文  参考訳（メタデータ） (2024-04-08T12:30:07Z)
• 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)
• Interactively Learning Preference Constraints in Linear Bandits [100.78514640066565]
  我々は、既知の報酬と未知の制約で逐次意思決定を研究する。 応用として,運転シミュレーションにおいて,人間の嗜好を表現するための学習制約を検討する。
  論文  参考訳（メタデータ） (2022-06-10T17:52:58Z)
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems [0.0]
  離散最適化問題(整数型最適化問題)を直感的に合成・解析する手法を提案する。 この方法は、符号化に依存しない離散量子中間表現(DQIR)を用いて表現される。 第二に、複数のランタイムエンコーディングを比較した数値的研究を行う。 第3に、我々は16レベルの量子変数までの低深度グラフ由来部分ミキサー(GDPM)を設計する。
  論文  参考訳（メタデータ） (2022-03-28T01:01:12Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• 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)
• Encoding Linear Constraints into SAT [0.0]
  複数値決定ダイアグラムとソートネットワークに基づく新しいSATエンコーディングを定義する。 線形整数解法 (MIP) よりも優れており, 適切な問題に対して LCG や SMT より優れている場合もある。
  論文  参考訳（メタデータ） (2020-05-05T11:37:43Z)
• Discovering Representations for Black-box Optimization [73.59962178534361]
  ブラックボックス最適化符号化は手作業で行うのではなく,自動的に学習可能であることを示す。 学習された表現は、標準的なMAP-Elitesよりも桁違いに少ない評価で高次元の問題を解くことができることを示す。
  論文  参考訳（メタデータ） (2020-03-09T20:06:20Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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