Fugu-MT 論文翻訳(概要): Integer Linear Programming Preprocessing for Maximum Satisfiability

論文の概要: 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)
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)
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)
torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
論文参考訳（メタデータ） (2024-02-06T02:33:00Z)
Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
論文参考訳（メタデータ） (2024-01-11T15:02:15Z)
Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文参考訳（メタデータ） (2023-01-19T18:24:08Z)
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)
Efficient Algorithms for Extreme Bandits [20.68824391770909]
我々は,学習者が最大の報酬を集めようとするマルチアーマッド・バンディットの変種であるExtreme Bandit問題に貢献する。まず、報酬分布の尾部における軽度の仮定の下で、i.d確率変数の最大値の濃度について検討する。次に,より適応性の高いQoMax-SDAアルゴリズムを提案し,解析する。
論文参考訳（メタデータ） (2022-03-21T11:09:34Z)
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)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Fault Tree Analysis: Identifying Maximum Probability Minimal Cut Sets with MaxSAT [0.342658286826597]
我々は,MPMCS問題を重み付き部分最大SAT問題としてモデル化し,並列SAT解決アーキテクチャを用いて解決する。オープンソースツールで得られた結果は,このアプローチが効率的かつ効率的であることを示唆している。
論文参考訳（メタデータ） (2020-05-05T19:47:15Z)

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