論文の概要: ILP Techniques for Enhancing Branch and Bound MaxSAT Solvers
- arxiv url: http://arxiv.org/abs/2506.06216v2
- Date: Tue, 08 Jul 2025 02:29:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-09 14:27:12.671226
- Title: ILP Techniques for Enhancing Branch and Bound MaxSAT Solvers
- Title（参考訳）: ILPによる分岐および境界MaxSATソルバーの高速化
- Authors: Jialu Zhang, Chu-Min Li, Sami Cherif, Shuolin Li, Zhifei Zheng,
- Abstract要約: ILP技術により、WMaxCDCL-OpenWbo1200とMaxCDCL-OpenWbo300はそれぞれ27と30のインスタンスを解決できる。
現状のMaxSATソルバはポートフォリオのICPソルバに大きく依存しているが,提案手法ではICPプリプロセッシング技術を用いて依存性を低減している。
提案した(W)MaxCDCLを含むポートフォリオ内の短いランタイムのみをILPソルバに割り当てることで,強力な結果が得られる。
- 参考スコア（独自算出の注目度）: 6.142313296799415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper investigates the impact of ILP techniques on BnB MaxSAT solvers, particularly ILP preprocessing techniques and various portfolio strategies. Experimental results demonstrate that ILP techniques enable WMaxCDCL-OpenWbo1200 and MaxCDCL-OpenWbo300, the best two solvers in the unweighted track of the MaxSAT evaluation 2024, to solve 27 and 30 additional instances, respectively. Furthermore, although state-of-the-art MaxSAT solvers heavily rely on an ILP solver in their portfolios, our proposed approach uses ILP preprocessing techniques to reduce this dependency. Allocating only a short runtime to the ILP solver within a portfolio that includes (W)MaxCDCL, as proposed in our approach, is sufficient to achieve strong results.
- Abstract（参考訳）: 本稿では,BnB MaxSATソルバ,特にILP前処理技術およびポートフォリオ戦略に対するILP手法の影響について検討する。
実験の結果,ILP技術により,最大CDCL-OpenWbo1200と最大CDCL-OpenWbo300の2つの解法が,最大SAT評価2024の未重み付きトラックでそれぞれ27と30の余分な問題を解けることがわかった。
さらに,現状の MaxSAT ソルバはポートフォリオの ILP ソルバに大きく依存しているが,提案手法では ILP プリプロセッシング技術を用いてその依存性を低減している。
提案した(W)MaxCDCLを含むポートフォリオ内の短いランタイムのみをILPソルバに割り当てることで,強力な結果が得られる。
関連論文リスト
- IGMaxHS -- An Incremental MaxSAT Solver with Support for XOR Clauses [0.0]
IGMaxHS は iMaxHS と GaussMaxHS をベースとしているが, XOR の制約は GaussMaxHS よりも少ない。
IGMaxHSは、不正な不満足な判断も、不正なモデルも、一貫性のないコストモデルの組み合わせも報告していない唯一の解決法である。
IGMaxHSは,ミュンヘン量子ツールキットを用いたシミュレーションにより,量子カラーコードを復号化可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T11:21:21Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Algorithmic Foundations of Empirical X-risk Minimization [51.58884973792057]
この原稿は、機械学習とAIの新しい最適化フレームワーク、bf empirical X-risk baseline (EXM)を紹介している。
Xリスク(X-risk)は、構成測度または目的の族を表すために導入された用語である。
論文 参考訳（メタデータ） (2022-06-01T12:22:56Z) - 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) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。