論文の概要: Advancing Weighted Partial MaxSAT Solving via Differentiable GPU Guidance
- arxiv url: http://arxiv.org/abs/2611.15091v1
- Date: Wed, 11 Nov 2026 06:09:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.061109
- Title: Advancing Weighted Partial MaxSAT Solving via Differentiable GPU Guidance
- Title(参考訳): 微分GPU誘導による部分マックスサット問題解決の強化
- Abstract要約: We present a GPU- CPU hybrid framework for Weighted partial MaxSAT (WPMAX-SAT)。
我々のフレームワークはGPU最適化変数ロジットを高信頼割当に変換し、2つの相補モードでCPUソルバに転送する。
本研究では, tt-open-wbo-inc-Glucoseで平均解のスコアを最大4.9%, SPB-MaxSAT-c-FPSで最大4.8%向上させる。
- 参考スコア(独自算出の注目度): 3.8631902723816647
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a GPU-CPU hybrid framework for Weighted Partial MaxSAT (WPMAX-SAT) that complements state-of-the-art CPU solvers with differentiable GPU optimization. The GPU stage directly optimizes instance-specific categorical decision parameters without a training dataset or a pretrained predictive model. The central challenge in extending differentiable optimization to WPMAX-SAT is the hard/soft clause asymmetry: hard clauses represent inviolable feasibility constraints while soft clauses carry weights. We introduce a hierarchical differentiable loss that prioritizes hard clause satisfaction before optimizing the weighted soft objective, ensuring that GPU gradient descent leans towards the constraint structure of WPMAX-SAT. Our framework transforms the GPU-optimized variable logits to high-confidence assignments and transfers them to CPU solvers via two complementary modes: partial guidance, which injects the most confident perturbed partial variable assignments as soft clauses into $N$ parallel solver instances, and phase initialization, which guides the CDCL solver's internal branching polarity with the full GPU assignment as a warm start to preserve the problem's originality. We evaluate on all 229 instances of the MSE 2024 (most recent due to cancellation in 2025) anytime weighted benchmark with the top 2 winners as baselines; our hybrid framework improves the average solution score by up to 4.9% over tt-open-wbo-inc-Glucose and 4.8% over SPB-MaxSAT-c-FPS at a 300-second time limit, with the potential to obtain better solutions surpassing the best known solution recorded in the competition evaluation.
- Abstract(参考訳): Weighted partial MaxSAT (WPMAX-SAT) のためのGPU-CPUハイブリッドフレームワークを提案する。
GPUステージは、トレーニングデータセットや事前訓練された予測モデルなしで、インスタンス固有のカテゴリ決定パラメータを直接最適化する。
WPMAX-SATへの微分可能最適化の拡張における中心的な課題は、ハード/ソフトな節非対称性である。
重み付けされたソフト目標を最適化する前に、ハード条項満足度を優先する階層的微分可能損失を導入し、GPU勾配勾配がWPMAX-SATの制約構造に傾くことを保証する。
筆者らのフレームワークは,GPU最適化変数のロジットを高信頼割当に変換し,2つの相補的なモードによりCPUソルバに転送する: 部分的ガイダンス,ソフト節として最も確実な摂動部分変数割当を$N$パラレルソルバインスタンスに注入する部分的ガイダンス,およびCDCLソルバの内部分岐極性を誘導する位相初期化。
MSE 2024のすべての229インスタンス(2025年のキャンセルによる最最近のもの)をベースラインとして評価し、我々のハイブリッドフレームワークは、tt-open-wbo-inc-Glucoseよりも4.9%、SPB-MaxSAT-c-FPSより4.8%、競争評価で記録された最もよく知られたソリューションより優れたソリューションを得る可能性が高く、平均解スコアを最大4.9%向上させる。
関連論文リスト
- Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks [20.951741111898897]
SDPソルバの原理的,軽量なニューラルプロキシとして機能する,Max-Cut固有のグラフニューラルネットワークを提案する。
我々のアーキテクチャは、最先端のSDPソルバであるMosekと比較して、正確なMax-Cut解のバウンディングコストを最大10.6ドル削減できることを示す。
論文 参考訳(メタデータ) (2026-05-08T01:41:40Z) - Diff3R: Feed-forward 3D Gaussian Splatting with Uncertainty-aware Differentiable Optimization [76.38917994186733]
Diff3Rはフィードフォワード予測とテストタイム最適化をブリッジする新しいフレームワークである。
フィードフォワード3DGSアーキテクチャにシームレスに統合でき、ポーズギヴン法とポーズフリー法の両方に対応できることを示す。
論文 参考訳(メタデータ) (2026-04-01T15:40:20Z) - Towards Robust Scaling Laws for Optimizers [89.21160945066737]
経験的スケーリング法則は、モデルのサイズやトレーニングデータの増加に伴って損失を予測するために広く使用されている。
本研究では, 損失分解を既約, 近似, 最適化誤差に分解した結果, チンチラ方式のスケーリング法則が自然に現れることを示す。
論文 参考訳(メタデータ) (2026-02-07T21:40:33Z) - Scalable Floating-Point Satisfiability via Staged Optimization [4.212975258164135]
この研究は浮動小数点満足度を解くための新しいアプローチであるStageSATを導入している。
StageSATは、浮動小数点公式を、精度の向上の3段階における一連の最適化問題として再設定する。
論文 参考訳(メタデータ) (2026-01-08T01:51:46Z) - Benchmarking Lie-Algebraic Pretraining and Non-Variational QWOA for the MaxCut Problem [4.103893081207555]
本稿では,トレーニング性向上を目的とした2つの戦略の比較性能解析を行う。
回路深さは200 Erds-Rényi および 200 3-正則グラフに対して 256$ である。
NV-QWOAはわずか60回で平均98.9%の近似比を獲得し、Lie-代数的事前訓練されたQWOAは500回で77.71%に改善された。
論文 参考訳(メタデータ) (2025-12-28T09:42:02Z) - TurboSAT: Gradient-Guided Boolean Satisfiability Accelerated on GPU-CPU Hybrid System [7.530665570222049]
最先端の満足度解決者は、本質的に競合駆動型検索アルゴリズムに大きく依存している。
ニューラルネットワークのトレーニングに着想を得て、SAT問題を二項行列行列行列乗法層として定式化する。
我々は、並列微分可能最適化とシーケンシャルサーチの長所を組み合わせて、ハイブリッドGPU-CPUシステムでSATを高速化する。
論文 参考訳(メタデータ) (2025-11-11T01:41:40Z) - ILP Techniques for Enhancing Branch and Bound MaxSAT Solvers [6.142313296799415]
ILP技術により、WMaxCDCL-OpenWbo1200とMaxCDCL-OpenWbo300はそれぞれ27と30のインスタンスを解決できる。
現状のMaxSATソルバはポートフォリオのICPソルバに大きく依存しているが,提案手法ではICPプリプロセッシング技術を用いて依存性を低減している。
提案した(W)MaxCDCLを含むポートフォリオ内の短いランタイムのみをILPソルバに割り当てることで,強力な結果が得られる。
論文 参考訳(メタデータ) (2025-06-06T16:21:38Z) - Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。
我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。
アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
論文 参考訳(メタデータ) (2022-10-31T17:59:29Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。