論文の概要: UpMax: User partitioning for MaxSAT

• arxiv url: http://arxiv.org/abs/2305.16191v1
• Date: Thu, 25 May 2023 15:50:00 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 14:11:47.238933
• Title: UpMax: User partitioning for MaxSAT
• Title（参考訳）: UpMax: MaxSATのユーザパーティショニング
• Authors: Pedro Orvalho and Vasco Manquinho and Ruben Martins
• Abstract要約: パーティショニングは、不満に基づくMaxSATアルゴリズムのパフォーマンスに大きな影響を与える。 本稿では,分割処理をMaxSATの解法から切り離すUpMaxという新しいフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 2.2022484178680872
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: It has been shown that Maximum Satisfiability (MaxSAT) problem instances can be effectively solved by partitioning the set of soft clauses into several disjoint sets. The partitioning methods can be based on clause weights (e.g., stratification) or based on graph representations of the formula. Afterwards, a merge procedure is applied to guarantee that an optimal solution is found. This paper proposes a new framework called UpMax that decouples the partitioning procedure from the MaxSAT solving algorithms. As a result, new partitioning procedures can be defined independently of the MaxSAT algorithm to be used. Moreover, this decoupling also allows users that build new MaxSAT formulas to propose partition schemes based on knowledge of the problem to be solved. We illustrate this approach using several problems and show that partitioning has a large impact on the performance of unsatisfiability-based MaxSAT algorithms.
• Abstract（参考訳）: 最大満足度(MaxSAT)問題インスタンスは、ソフト節の集合を複数の非結合集合に分割することで効果的に解決できることが示されている。 分割法は節重み(例えば階層化)に基づいてもよいし、公式のグラフ表現にもとづくこともできる。 その後、最適解が見つかることを保証するためにマージ手順が適用される。 本稿では,分割処理をMaxSATの解法から切り離すUpMaxという新しいフレームワークを提案する。 結果として、新しいパーティショニング手順は、使用するMaxSATアルゴリズムとは独立して定義することができる。 さらに、このデカップリングにより、ユーザーは新しいMaxSAT公式を構築し、解決すべき問題の知識に基づいて分割スキームを提案できる。 このアプローチをいくつかの問題を用いて説明し、分割が不満足なMaxSATアルゴリズムの性能に大きな影響を与えることを示す。

関連論文リスト

• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。 提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。 本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
  論文  参考訳（メタデータ） (2023-04-28T07:09:23Z)
• Incorporating Multi-armed Bandit with Local Search for MaxSAT [16.371916145216737]
  MaxSAT問題の2つの一般化: partial MaxSAT (PMS) と Weighted PMS (WPMS) そこで本稿では,BandHSと呼ばれる局所探索アルゴリズムを提案する。 これら2つの帯域は、実現不可能な解空間と実現不可能な解空間の両方において、アルゴリズムの探索能力を向上させることができる。
  論文  参考訳（メタデータ） (2022-11-29T08:19:26Z)
• DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving [45.21499915442282]
  本稿では,ハイブリッド制約を用いた一般化MaxSAT問題の解法について,新しい動的プログラミング手法を提案する。 我々の汎用フレームワークは、MaxSAT、Min-MaxSAT、MinSATといったCNF-MaxSATの多くの一般化をハイブリッド制約で認めている。 実験の結果、DPMSは様々な手法に基づく他のアルゴリズムがすべて失敗し、特定の問題を迅速に解決できることがわかった。
  論文  参考訳（メタデータ） (2022-05-08T00:31:53Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• Fault Tree Analysis: Identifying Maximum Probability Minimal Cut Sets with MaxSAT [0.342658286826597]
  我々は,MPMCS問題を重み付き部分最大SAT問題としてモデル化し,並列SAT解決アーキテクチャを用いて解決する。 オープンソースツールで得られた結果は,このアプローチが効率的かつ効率的であることを示唆している。
  論文  参考訳（メタデータ） (2020-05-05T19:47:15Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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