Fugu-MT 論文翻訳(概要): Extracting Problem Structure with LLMs for Optimized SAT Local Search

論文の概要: Extracting Problem Structure with LLMs for Optimized SAT Local Search

arxiv url: http://arxiv.org/abs/2501.14630v2
Date: Tue, 04 Feb 2025 13:55:19 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-05 14:54:54.751797
Title: Extracting Problem Structure with LLMs for Optimized SAT Local Search
Title（参考訳）: 最適化SAT局所探索のためのLLMによる問題構造抽出
Authors: André Schidler, Stefan Szeider,
Abstract要約: ローカル検索前処理は、Conflict-Driven Clause Learning (CDCL)を高速化する。本稿では,Large Language Models (LLM) を用いてPythonの符号化コードを解析する手法を提案する。本手法は,隠れ構造パターンを見つけるための局所探索アルゴリズムを自動生成する。
参考スコア（独自算出の注目度）: 25.363456168714904
License:
Abstract: Local search preprocessing makes Conflict-Driven Clause Learning (CDCL) solvers faster by providing high-quality starting points and modern SAT solvers have incorporated this technique into their preprocessing steps. However, these tools rely on basic strategies that miss the structural patterns in problems. We present a method that applies Large Language Models (LLMs) to analyze Python-based encoding code. This reveals hidden structural patterns in how problems convert into SAT. Our method automatically generates specialized local search algorithms that find these patterns and use them to create strong initial assignments. This works for any problem instance from the same encoding type. Our tests show encouraging results, achieving faster solving times compared to baseline preprocessing systems.
Abstract（参考訳）: ローカル検索前処理は、高品質な開始点を提供することで、Conflict-Driven Clause Learning (CDCL)ソルバを高速化する。しかし、これらのツールは、問題の構造パターンを見逃す基本的な戦略に依存している。本稿では,Large Language Models (LLM) を用いてPythonの符号化コードを解析する手法を提案する。これにより、問題がどのようにSATに変換されるかにおいて、隠れた構造パターンが明らかになる。提案手法は,これらのパターンを見つけ出し,それを用いて強力な初期代入を生成する特殊な局所探索アルゴリズムを自動生成する。これは、同じエンコーディングタイプからの任意の問題インスタンスに対して機能する。本試験は, ベースライン前処理システムと比較して, 高速な解解解時間を達成できることを示す。

関連論文リスト

CASET: Complexity Analysis using Simple Execution Traces for CS* submissions [0.0]
CS1 や CS2 コースで学生の提出を自動アップグレードする最も一般的な方法は、事前に定義されたテストスイートに対して実行し、結果と参照結果を比較することである。この手法は、解の正しさが、結果を得るために使われるアルゴリズムのような単純な出力を超えると利用できない。動的トレースと教師なし機械学習を用いてアルゴリズムの時間的複雑さを解析する新しいツールCASETを提案する。
論文参考訳（メタデータ） (2024-10-20T15:29:50Z)
A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
論文参考訳（メタデータ） (2024-07-17T21:26:27Z)
The CLRS-Text Algorithmic Reasoning Language Benchmark [48.45201665463275]
CLRS-TextはCLRSベンチマークのテキストバージョンである。 CLRS-Textは、30の多様な、挑戦的なアルゴリズムタスクのためのトレースデータを手続き的に生成することができる。このベンチマークでは、様々なLMをジェネラリストエグゼクタとして微調整し評価する。
論文参考訳（メタデータ） (2024-06-06T16:29:25Z)
General Method for Solving Four Types of SAT Problems [12.28597116379225]
既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
論文参考訳（メタデータ） (2023-12-27T06:09:48Z)
Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
論文参考訳（メタデータ） (2023-09-20T16:27:52Z)
Machine Learning for SAT: Restricted Heuristics and New Graph Representations [0.8870188183999854]
SATは、自動スケジューリングを含む多くのアプリケーションにおいて、基本的なNP完全問題である。大きなインスタンスを解決するためには、SATソルバは、例えばDPLLとCDCLソルバの分岐変数を選択するなど、ブールアンに依存する必要がある。我々は、訓練されたMLモデルでいくつかの初期ステップを行い、古典的なランタイムに制御をリリースする戦略を提案する。
論文参考訳（メタデータ） (2023-07-18T10:46:28Z)
Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning [75.74103236299477]
CoT(Chain-of- Thought prompting)とツール拡張は、大きな言語モデルを改善するための効果的なプラクティスとして検証されている。ツールインターフェース,すなわち textbfDELI を用いた推論ステップを考慮に入れた新しい手法を提案する。 CARPと他の6つのデータセットの実験結果から、提案されたDELIは、主に競合ベースラインを上回っていることが示された。
論文参考訳（メタデータ） (2023-06-04T17:02:59Z)
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)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
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)

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