論文の概要: Integer Linear Programming Preprocessing for Maximum Satisfiability
- arxiv url: http://arxiv.org/abs/2506.06216v1
- Date: Fri, 06 Jun 2025 16:21:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-09 17:28:43.551969
- Title: Integer Linear Programming Preprocessing for Maximum Satisfiability
- Title（参考訳）: 最大満足度のための整数線形計画前処理
- Authors: Jialu Zhang, Chu-Min Li, Sami Cherif, Shuolin Li, Zhifei Zheng,
- Abstract要約: 最近のMaxSAT評価では、ほとんどのMaxSATソルバはポートフォリオの一部としてILPソルバを採用している。
本稿では,Linear Programming (ILP) プリプロセッシング技術がMaxSAT解決に与える影響について検討する。
- 参考スコア（独自算出の注目度）: 6.142313296799415
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Maximum Satisfiability problem (MaxSAT) is a major optimization challenge with numerous practical applications. In recent MaxSAT evaluations, most MaxSAT solvers have adopted an ILP solver as part of their portfolios. This paper investigates the impact of Integer Linear Programming (ILP) preprocessing techniques on MaxSAT solving. Experimental results show that ILP preprocessing techniques help WMaxCDCL-OpenWbo1200, the winner of the MaxSAT evaluation 2024 in the unweighted track, solve 15 additional instances. Moreover, current state-of-the-art MaxSAT solvers heavily use an ILP solver in their portfolios, while our proposed approach reduces the need to call an ILP solver in a portfolio including WMaxCDCL or MaxCDCL.
- Abstract（参考訳）: 最大満足度問題(MaxSAT)は、多くの実用的な応用において大きな最適化課題である。
最近のMaxSAT評価では、ほとんどのMaxSATソルバはポートフォリオの一部としてILPソルバを採用している。
Integer Linear Programming (ILP) の前処理技術がMaxSAT解決に与える影響について検討する。
実験の結果、ICP前処理技術は、未加重トラックでの最大SAT評価2024の勝者であるWMaxCDCL-OpenWbo1200に有効であることが判明した。
さらに,現在最先端の MaxSAT ソルバはポートフォリオで ILP ソルバを多用しているが,提案手法では WMaxCDCL や 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。