論文の概要: torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem

• arxiv url: http://arxiv.org/abs/2402.03640v1
• Date: Tue, 6 Feb 2024 02:33:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-07 16:55:11.740659
• Title: torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem
• Title（参考訳）: torchmSAT: 最大満足度問題に対するGPU加速近似
• Authors: Abdelrahman Hosny, Sherief Reda
• Abstract要約: 最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
• 参考スコア（独自算出の注目度）: 1.5850859526672516
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The remarkable achievements of machine learning techniques in analyzing discrete structures have drawn significant attention towards their integration into combinatorial optimization algorithms. Typically, these methodologies improve existing solvers by injecting learned models within the solving loop to enhance the efficiency of the search process. In this work, we derive a single differentiable function capable of approximating solutions for the Maximum Satisfiability Problem (MaxSAT). Then, we present a novel neural network architecture to model our differentiable function, and progressively solve MaxSAT using backpropagation. This approach eliminates the need for labeled data or a neural network training phase, as the training process functions as the solving algorithm. Additionally, we leverage the computational power of GPUs to accelerate these computations. Experimental results on challenging MaxSAT instances show that our proposed methodology outperforms two existing MaxSAT solvers, and is on par with another in terms of solution cost, without necessitating any training or access to an underlying SAT solver. Given that numerous NP-hard problems can be reduced to MaxSAT, our novel technique paves the way for a new generation of solvers poised to benefit from neural network GPU acceleration.
• Abstract（参考訳）: 離散構造解析における機械学習技術の顕著な成果は、組合せ最適化アルゴリズムへの統合に大きな注目を集めている。 通常、これらの手法は、学習したモデルを解法ループ内に注入することで既存の解法を改善する。 本研究では,最大満足度問題(MaxSAT)の解を近似できる単一微分可能関数を導出する。 そこで我々は,我々の微分可能な関数をモデル化するための新しいニューラルネットワークアーキテクチャを提案する。 このアプローチでは、トレーニングプロセスが解決アルゴリズムとして機能するため、ラベル付きデータやニューラルネットワークトレーニングフェーズが不要になる。 さらに,GPUの計算能力を利用して計算を高速化する。 MaxSATインスタンスに挑戦する実験結果から,提案手法は既存の2つのMaxSATソルバよりも優れており,学習や基盤となるSATソルバへのアクセスを必要とせず,ソリューションコストの面で同等であることがわかった。 NPハード問題をMaxSATに還元できることを考えると、我々の新しい手法は、ニューラルネットワークGPUアクセラレーションの恩恵を受ける新しい世代の問題解決者への道を開くものである。

関連論文リスト

• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
  論文  参考訳（メタデータ） (2023-10-01T00:12:31Z)
• Training Neural Networks using SAT solvers [1.0152838128195465]
  本稿では,SATソルバを用いてニューラルネットワークのトレーニングを行うグローバル最適化手法を提案する。 実験では,パリティ学習などのタスクにおいて,ADAMオプティマイザに対するアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2022-06-10T01:31:12Z)
• 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)
• ML Supported Predictions for SAT Solvers Performance [0.0]
  内部のソルバランタイムパラメータが収集され、分析されている。 問題解決者の終了動作のバイナリ分類のための機械学習モデルが作成されている。
  論文  参考訳（メタデータ） (2021-12-17T11:17:29Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT [0.0]
  本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-10T07:59:54Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)

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

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