論文の概要: STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2506.11057v1
• Date: Thu, 22 May 2025 15:37:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-22 23:32:14.527727
• Title: STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
• Title（参考訳）: STRCMP:組合せ最適化のための言語モデルとグラフ構造優先事項の統合
• Authors: Xijun Li, Jiexiang Yang, Jinghao Wang, Bo Peng, Jianguo Yao, Haibing Guan,
• Abstract要約: 演算研究と理論計算機科学の中心となる組合せ最適化(CO)問題は、NPハードな性質のため、重要な計算課題を提示する。 本稿では,StRCMPを提案する。STRCMPは,構造先行を体系的に統合し,解の質と解解効率を向上する新しい構造対応アルゴリズム探索フレームワークである。 我々のフレームワークは、COインスタンスから構造埋め込みを抽出するグラフニューラルネットワーク(GNN)と、これらの埋め込みを条件としたLLMを組み合わせることで、ソルバ固有コードの形で高い性能のアルゴリズムを識別する。
• 参考スコア（独自算出の注目度）: 18.162186876640764
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Combinatorial optimization (CO) problems, central to operation research and theoretical computer science, present significant computational challenges due to their NP-hard nature. While large language models (LLMs) have emerged as promising tools for CO--either by directly generating solutions or synthesizing solver-specific codes--existing approaches often neglect critical structural priors inherent to CO problems, leading to suboptimality and iterative inefficiency. Inspired by human experts' success in leveraging CO structures for algorithm design, we propose STRCMP, a novel structure-aware LLM-based algorithm discovery framework that systematically integrates structure priors to enhance solution quality and solving efficiency. Our framework combines a graph neural network (GNN) for extracting structural embeddings from CO instances with an LLM conditioned on these embeddings to identify high-performing algorithms in the form of solver-specific codes. This composite architecture ensures syntactic correctness, preserves problem topology, and aligns with natural language objectives, while an evolutionary refinement process iteratively optimizes generated algorithm. Extensive evaluations across Mixed Integer Linear Programming and Boolean Satisfiability problems, using nine benchmark datasets, demonstrate that our proposed STRCMP outperforms five strong neural and LLM-based methods by a large margin, in terms of both solution optimality and computational efficiency. The code and learned model will be publicly available upon the acceptance of the paper.
• Abstract（参考訳）: 演算研究と理論計算機科学の中心となる組合せ最適化(CO)問題は、NPハードな性質のため、重要な計算課題を提示する。 大規模言語モデル(LLM)は、ソリューションを直接生成したり、解決者固有のコードを合成することによって、COにとって有望なツールとして現れてきた。 アルゴリズム設計におけるCO構造を活用した人間専門家の成功に触発されて,STRCMPを提案する。STRCMPは,構造先行を体系的に統合し,解の質を高め,解解効率を向上する新しい構造対応LLMアルゴリズム発見フレームワークである。 我々のフレームワークは、COインスタンスから構造埋め込みを抽出するグラフニューラルネットワーク(GNN)と、これらの埋め込みを条件としたLLMを組み合わせることで、ソルバ固有コードの形で高い性能のアルゴリズムを識別する。 この複合アーキテクチャは、構文的正確性を確保し、問題トポロジを保持し、自然言語の目的と整合し、進化的洗練プロセスは生成されたアルゴリズムを反復的に最適化する。 混合整数線形計画法とブール満足度問題を9つのベンチマークデータセットを用いて総合評価した結果,提案したSTRCMPは,解の最適性と計算効率の両面から,5つの強力なニューラルおよびLLMベースの手法よりも高い性能を示した。 コードと学習モデルは、論文の受理時に公開される。

関連論文リスト

• Large Language Models for Design Structure Matrix Optimization [4.513609458468522]
  複雑なエンジニアリングシステムでは、設計構造行列(DSM)を用いてコンポーネントや開発活動間の相互依存性をモデル化し分析することが多い。 フィードバックループを最小限に抑え、モジュール性やプロセス効率を向上させるためにDSM内の要素を再編成することは、エンジニアリング設計と運用において困難な最適化問題となっている。 本研究では, 大規模言語モデル (LLM) が, 高度な推論や文脈理解にその能力を活用することで, そうしたCO問題の解決を支援する可能性について検討する。
  論文  参考訳（メタデータ） (2025-06-11T13:53:35Z)
• From Understanding to Excelling: Template-Free Algorithm Design through Structural-Functional Co-Evolution [39.42526347710991]
  大規模言語モデル(LLM)はアルゴリズム生成と最適化の自動化を大幅に加速した。 LLMに基づくエンドツーエンドのアルゴリズム生成と最適化フレームワークを提案する。 我々のアプローチは、LLMの深い意味理解を利用して、自然言語の要求や人間による論文をコードソリューションに変換する。
  論文  参考訳（メタデータ） (2025-03-13T08:26:18Z)
• Large Language Models for Combinatorial Optimization of Design Structure Matrix [4.513609458468522]
  エンジニアリングアプリケーションの効率と性能を改善するためには、組合せ最適化(CO)が不可欠である。 実世界の工学的問題に関しては、純粋数学的推論に基づくアルゴリズムは限定的であり、最適化に必要な文脈ニュアンスを捉えることができない。 本研究では,工学的CO問題の解法におけるLarge Language Models (LLMs) の可能性について,その推論能力と文脈的知識を活用して検討する。
  論文  参考訳（メタデータ） (2024-11-19T15:39:51Z)
• On the Design and Analysis of LLM-Based Algorithms [74.7126776018275]
  大規模言語モデル(LLM)はアルゴリズムのサブルーチンとして使用される。 LLMは素晴らしい経験的成功を収めた。 提案フレームワークは,LLMアルゴリズムの進歩を約束する。
  論文  参考訳（メタデータ） (2024-07-20T07:39:07Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。 性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
  論文  参考訳（メタデータ） (2022-05-03T07:54:56Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

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

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