論文の概要: Enhancing Local Search for MaxSAT with Deep Differentiation Clause Weighting

• arxiv url: http://arxiv.org/abs/2512.05619v1
• Date: Fri, 05 Dec 2025 11:02:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-13 22:40:56.999198
• Title: Enhancing Local Search for MaxSAT with Deep Differentiation Clause Weighting
• Title（参考訳）: 深部微分クロース重み付きMaxSATの局所探索の強化
• Authors: Menghua Jiang, Haokai Gao, Shuhao Chen, Yin Chen,
• Abstract要約: 部分最大満足度(PMS)と重み付けされた部分最大満足度(WPMS)は、幅広い現実世界の応用に一般化される。 既存の方法は、しばしばPMSとWPMSを適切に区別できない。 本稿では,PMSとWPMSの条項重み付けを異なる条件で更新する新しい条項重み付け方式を提案する。
• 参考スコア（独自算出の注目度）: 2.426267795975439
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Partial Maximum Satisfiability (PMS) and Weighted Partial Maximum Satisfiability (WPMS) generalize Maximum Satisfiability (MaxSAT), with broad real-world applications. Recent advances in Stochastic Local Search (SLS) algorithms for solving (W)PMS have mainly focused on designing clause weighting schemes. However, existing methods often fail to adequately distinguish between PMS and WPMS, typically employing uniform update strategies for clause weights and overlooking critical structural differences between the two problem types. In this work, we present a novel clause weighting scheme that, for the first time, updates the clause weights of PMS and WPMS instances according to distinct conditions. This scheme also introduces a new initialization method, which better accommodates the unique characteristics of both instance types. Furthermore, we propose a decimation method that prioritizes satisfying unit and hard clauses, effectively complementing our proposed clause weighting scheme. Building on these methods, we develop a new SLS solver for (W)PMS named DeepDist. Experimental results on benchmarks from the anytime tracks of recent MaxSAT Evaluations show that DeepDist outperforms state-of-the-art SLS solvers. Notably, a hybrid solver combining DeepDist with TT-Open-WBO-Inc surpasses the performance of the MaxSAT Evaluation 2024 winners, SPB-MaxSAT-c-Band and SPB-MaxSAT-c-FPS, highlighting the effectiveness of our approach. The code is available at https://github.com/jmhmaxsat/DeepDist
• Abstract（参考訳）: 部分最大満足度 (PMS) と重み付き部分最大満足度 (WPMS) は、幅広い実世界の応用で最大満足度 (MaxSAT) を一般化する。 確率的局所探索(SLS)アルゴリズムの最近の進歩は、主に節重み付け方式の設計に焦点を当てている。 しかしながら、既存の手法では、PMSとWPMSを適切に区別することができず、通常、条項の重みに対する一様更新戦略を採用し、2つの問題タイプ間の重要な構造的違いを見落としている。 本研究では, PMS と WPMS インスタンスの重み付けを異なる条件で更新する新しい条項重み付け方式を提案する。 このスキームはまた、両方のインスタンスタイプのユニークな特性をよりよく適合させる新しい初期化手法も導入している。 さらに,満足度の高い単位節とハード節を優先するデシメーション手法を提案し,提案した節重み付け方式を効果的に補完する。 これらの手法に基づいて,DeepDistと呼ばれる(W)PMSのための新しいSLSソルバを開発した。 最近のMaxSAT評価の任意のトラックからのベンチマーク実験の結果、DeepDistは最先端のSLSソルバよりも優れていた。 特に、DeepDistとTT-Open-WBO-Incを組み合わせたハイブリッドソルバは、MaxSAT Evaluation 2024の勝者、SPB-MaxSAT-c-Band、SPB-MaxSAT-c-FPSの性能を上回り、我々のアプローチの有効性を強調している。 コードはhttps://github.com/jmhmaxsat/DeepDistで入手できる。

関連論文リスト

• BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms [101.9736063064503]
  大規模言語モデル(LLM)の推論を高速化する一般的な手法として、投機的復号法が登場した。 本稿では,テキスト生成時に投機的復号化のためのハイパーパラメータの設定を適応的に選択する学習自由オンライン学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-05-21T05:56:31Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。 このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
  論文  参考訳（メタデータ） (2024-10-03T18:12:29Z)
• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• 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)
• 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)
• Contrastive Proposal Extension with LSTM Network for Weakly Supervised Object Detection [52.86681130880647]
  画像レベルのラベルしか使用せず、膨大なアノテーションコストを節約できるため、WSOD (Weakly supervised Object Detection) が注目されている。 本稿では,初期提案と拡張提案を比較して,初期提案を最適化する手法を提案する。 PASCAL VOC 2007 と VOC 2012 と MS-COCO のデータセットを用いた実験により,本手法は最先端の結果を得た。
  論文  参考訳（メタデータ） (2021-10-14T16:31:57Z)
• Farsighted Probabilistic Sampling based Local Search for (Weighted) Partial MaxSAT [5.529868797285073]
  部分マックスSAT (PMS) と重み付き部分マックスSAT (WPMS) は、マックスSATの典型的な問題に対する実用的な一般化である。 本稿では,この2つの問題を解くために,FPSと呼ばれる効率的な遠視的確率的サンプリングに基づく局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-23T07:41:56Z)

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

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