論文の概要: BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit

• arxiv url: http://arxiv.org/abs/2201.05544v1
• Date: Fri, 14 Jan 2022 16:32:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-17 16:54:12.947208
• Title: BandMaxSAT: A Local Search MaxSAT Solver with Multi-armed Bandit
• Title（参考訳）: BandMaxSAT: マルチアームバンド付きローカル検索MaxSATソルバー
• Authors: Jiongzhi Zheng and Kun He and Jianrong Zhou and Yan Jin and Chu-min Li and Felip Manya
• Abstract要約: そこで我々はBandMaxSATという局所探索アルゴリズムを提案する。 広汎な実験により、BandMaxSATは最先端(W)PMS局所探索アルゴリズムSATLike3.0を大きく上回っていることが示された。 その結果、BandMaxSAT-cはSATLike-c、Loandra、TT-Open-WBO-Incなど、最先端の完全(W)PMSソルバよりも優れている。
• 参考スコア（独自算出の注目度）: 16.371916145216737
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We address Partial MaxSAT (PMS) and Weighted PMS (WPMS), two practical generalizations of the MaxSAT problem, and propose a local search algorithm called BandMaxSAT, that applies a multi-armed bandit to guide the search direction, for these problems. The bandit in our method is associated with all the soft clauses in the input (W)PMS instance. Each arm corresponds to a soft clause. The bandit model can help BandMaxSAT to select a good direction to escape from local optima by selecting a soft clause to be satisfied in the current step, that is, selecting an arm to be pulled. We further propose an initialization method for (W)PMS that prioritizes both unit and binary clauses when producing the initial solutions. Extensive experiments demonstrate that BandMaxSAT significantly outperforms the state-of-the-art (W)PMS local search algorithm SATLike3.0. Specifically, the number of instances in which BandMaxSAT obtains better results is about twice that obtained by SATLike3.0. We further combine BandMaxSAT with the complete solver TT-Open-WBO-Inc. The resulting solver BandMaxSAT-c also outperforms some of the best state-of-the-art complete (W)PMS solvers, including SATLike-c, Loandra and TT-Open-WBO-Inc.
• Abstract（参考訳）: そこで我々は,MaxSAT問題の2つの実用的な一般化であるPartial MaxSAT (PMS) と Weighted PMS (WPMS) に対処し,これらの問題に対する探索方向の導出にマルチアームバンディットを適用したBandMaxSATと呼ばれる局所探索アルゴリズムを提案する。 提案手法のバンディットは入力(W)PMSインスタンスのすべてのソフト節と関連付けられている。 各アームはソフトな節に対応する。 バンドイットモデルは、現在のステップ、すなわち引き出すアームを選択する際に満足するソフト節を選択することにより、バンドイットが局所視眼から脱出するための良い方向を選択するのを助けることができる。 さらに,初期解を生成する際に,単位節とバイナリ節の両方を優先する(w)pmsの初期化手法を提案する。 広汎な実験により、BandMaxSATは最先端(W)PMS局所探索アルゴリズムSATLike3.0を大きく上回っている。 具体的には、BandMaxSATがより良い結果を得るインスタンス数はSATLike3.0の約2倍である。 さらに、BandMaxSATと完全な解決器TT-Open-WBO-Incを組み合わせる。 その結果、BandMaxSAT-cはSATLike-c、Loandra、TT-Open-WBO-Incなど、最先端の完全(W)PMSソルバよりも優れている。

関連論文リスト

• 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)
• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search [10.70006528984961]
  UCTMAXSAT上でのアルゴリズム的バリエーションを2つ紹介する。 まず、Nested Monte Carlo Searchアルゴリズムにインスパイアされた木探索のネストは、ベンチマークのほとんどのインスタンスタイプに有効である。 第二に、SLSの静的フリップ制限を用いることで、理想的な予算はインスタンスサイズに大きく依存し、動的に設定することを提案する。
  論文  参考訳（メタデータ） (2023-02-26T03:37:26Z)
• 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)
• 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)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

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

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