論文の概要: NLocalSAT: Boosting Local Search with Solution Prediction

• arxiv url: http://arxiv.org/abs/2001.09398v4
• Date: Wed, 9 Dec 2020 07:01:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-06 19:25:01.833039
• Title: NLocalSAT: Boosting Local Search with Solution Prediction
• Title（参考訳）: NLocalSAT: ソリューション予測によるローカル検索の強化
• Authors: Wenjie Zhang, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang
• Abstract要約: SAT問題の解決に有効な方法は局所探索 (SLS) である。 この方法はランダムな方法で割り振られ、SLSソルバの有効性に影響を与える。 NLocalSATは、SLSとソリューション予測モデルを組み合わせることで、ニューラルネットワークによる初期化割り当てを変更することで、SLSを向上する。 NLocalSATのソルバは元のSLSソルバよりも27% 62%改善した。
• 参考スコア（独自算出の注目度）: 36.69915361918781
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Boolean satisfiability problem (SAT) is a famous NP-complete problem in computer science. An effective way for solving a satisfiable SAT problem is the stochastic local search (SLS). However, in this method, the initialization is assigned in a random manner, which impacts the effectiveness of SLS solvers. To address this problem, we propose NLocalSAT. NLocalSAT combines SLS with a solution prediction model, which boosts SLS by changing initialization assignments with a neural network. We evaluated NLocalSAT on five SLS solvers (CCAnr, Sparrow, CPSparrow, YalSAT, and probSAT) with instances in the random track of SAT Competition 2018. The experimental results show that solvers with NLocalSAT achieve 27% ~ 62% improvement over the original SLS solvers.
• Abstract（参考訳）: ブール満足度問題(英: Boolean satisfiability problem、SAT)は、コンピュータ科学におけるNP完全問題である。 SAT問題を解く効果的な方法は確率的局所探索(SLS)である。 しかし、この手法では初期化をランダムに割り当て、SLSソルバの有効性に影響を与える。 この問題に対処するため,NLocalSATを提案する。 NLocalSATは、SLSとソリューション予測モデルを組み合わせることで、ニューラルネットワークによる初期化割り当てを変更することで、SLSを促進する。 NLocalSATを5つのSLSソルバ(CCAnr, Sparrow, CPSparrow, YalSAT, probSAT)で評価した。 実験の結果,NLocalSATは元のSLSソルバよりも27%～62%改善した。

関連論文リスト

• SibylSat: Using SAT as an Oracle to Perform a Greedy Search on TOHTN Planning [2.2276906461400054]
  本稿では,全順序付きHTN問題(TOHTN)を効率的に解くためのSATベースの新しい手法であるSibylSatを提案する。 広く普及しているSATベースのHTNプランナとは対照的に,SibylSatでは,拡張のための有望な分解を識別可能な,フレディな検索アプローチを採用している。 実験により、SybylSatは既存のSATベースのTOHTNアプローチよりも、ほとんどのIPCベンチマークで実行時と計画品質の両方において優れていることが示された。
  論文  参考訳（メタデータ） (2024-11-04T12:37:59Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks [7.951021955925275]
  グラフニューラルネットワーク(GNN)は、ブール満足度問題(SAT)を解決するための有望なアプローチとして登場した。 G4SATBenchは、GNNベースのSATソルバの包括的な評価フレームワークを確立する最初のベンチマーク研究である。 本結果は,GNNベースのSATソルバの性能に関する貴重な知見を提供する。
  論文  参考訳（メタデータ） (2023-09-29T02:50:57Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Addressing Variable Dependency in GNN-based SAT Solving [19.38746341365531]
  本稿では、繰り返しニューラルネットワークを統合したGNNベースのアーキテクチャであるAsymSATを提案し、可変代入に対する依存予測を生成する。 実験結果から,大規模テストセット上でのSATインスタンスの解数を改善することにより,依存変数予測がGNN方式の解解能力を拡張できることが示唆された。
  論文  参考訳（メタデータ） (2023-04-18T05:33:33Z)
• Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits [58.83758257568434]
  LEC インスタンスの SAT 符号化の硬さは SAT パーティショニングでは textitw.r. と推定できることを示す。 そこで本研究では, SAT符号化の難易度を精度良く推定できるパーティショニング法を提案する。
  論文  参考訳（メタデータ） (2022-10-04T09:19:13Z)
• SATformer: Transformer-Based UNSAT Core Learning [0.0]
  本稿では,SAT 問題に対する Transformer ベースのアプローチである SATformer を紹介する。 SATformerは、問題を直接解決するのではなく、満足できないことに焦点をあてて、その問題を反対方向からアプローチする。 SATformerは、シングルビットの満足度結果と最小限の不満コアを使用して、マルチタスク学習アプローチでトレーニングされる。 実験の結果,SATformerは既存のソルバのランタイムを平均21.33%削減できることがわかった。
  論文  参考訳（メタデータ） (2022-09-02T11:17:39Z)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Improving probability selecting based weights for Satisfiability Problem [6.59413630027528]
  ランダム k-SAT と HRS に対して,SelectNTS という新しい SLS アルゴリズムを提案する。 我々のアルゴリズムは最先端のランダムSATアルゴリズムより優れており、SelectNTSはランダムk-SATとHRSの両方を効果的に解くことができる。
  論文  参考訳（メタデータ） (2020-07-30T02:23:07Z)

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

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