論文の概要: Large Language Models as End-to-end Combinatorial Optimization Solvers

• arxiv url: http://arxiv.org/abs/2509.16865v1
• Date: Sun, 21 Sep 2025 01:30:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-23 18:58:16.011613
• Title: Large Language Models as End-to-end Combinatorial Optimization Solvers
• Title（参考訳）: エンドツーエンドの組合せ最適化解としての大規模言語モデル
• Authors: Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, Yingqian Zhang,
• Abstract要約: 物流や製造などの意思決定シナリオの中心となる組合せ最適化(CO)問題は、伝統的に問題固有のアルゴリズムを使用して解決される。 既存のアプローチは、コード生成やソルバ呼び出しといった中間ステップに依存しており、その汎用性とアクセシビリティを制限している。 本稿では,大規模言語モデル(LLM)を,自然言語問題記述をソリューションに直接マッピングすることで,エンドツーエンドのCOソルバとして機能させる,新たなフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 45.32050615257007
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization (CO) problems, central to decision-making scenarios like logistics and manufacturing, are traditionally solved using problem-specific algorithms requiring significant domain expertise. While large language models (LLMs) have shown promise in automating CO problem solving, existing approaches rely on intermediate steps such as code generation or solver invocation, limiting their generality and accessibility. This paper introduces a novel framework that empowers LLMs to serve as end-to-end CO solvers by directly mapping natural language problem descriptions to solutions. We propose a two-stage training strategy: supervised fine-tuning (SFT) imparts LLMs with solution generation patterns from domain-specific solvers, while a feasibility-and-optimality-aware reinforcement learning (FOARL) process explicitly mitigates constraint violations and refines solution quality. Evaluation across seven NP-hard CO problems shows that our method achieves a high feasibility rate and reduces the average optimality gap to 1.03-8.20% by tuning a 7B-parameter LLM, surpassing both general-purpose LLMs (e.g., GPT-4o), reasoning models (e.g., DeepSeek-R1), and domain-specific heuristics. Our method establishes a unified language-based pipeline for CO without extensive code execution or manual architectural adjustments for different problems, offering a general and language-driven alternative to traditional solver design while maintaining relative feasibility guarantees.
• Abstract（参考訳）: 物流や製造などの意思決定シナリオの中心となる組合せ最適化(CO)問題は、伝統的に、重要なドメインの専門知識を必要とする問題固有のアルゴリズムを使用して解決される。 大規模言語モデル(LLM)はCO問題解決の自動化を約束しているが、既存のアプローチはコード生成やソルバ呼び出しといった中間ステップに依存しており、その汎用性とアクセシビリティを制限している。 本稿では,LLMが自然言語問題記述をソリューションに直接マッピングすることで,エンドツーエンドのCOソルバとして機能することを可能にする新しいフレームワークを提案する。 教師付き微調整(SFT)は、ドメイン固有の解法からソリューション生成パターンをLLMに付与する一方、実行可能性と最適性を考慮した強化学習(FOARL)プロセスは、制約違反を明示的に軽減し、ソリューション品質を向上する。 7 つの NP-hard CO 問題に対して評価した結果,提案手法は高い実現率を実現し,平均最適性ギャップを 1.03-8.20% に低減し,汎用 LLM (eg , GPT-4o) および推論モデル (eg , DeepSeek-R1) およびドメイン固有ヒューリスティックス (ドメイン固有ヒューリスティックス) を超越した 7B-parameter LLM をチューニングした。 提案手法は,コード実行や異なる問題に対する手作業によるアーキテクチャ調整を伴わずに,COのための統一的な言語ベースパイプラインを構築し,相対的な実現可能性を確保しつつ,従来の問題解決設計に代わる汎用的かつ言語駆動的な代替手段を提供する。

関連論文リスト

• Learn to Relax with Large Language Models: Solving Nonlinear Combinatorial Optimization Problems via Bidirectional Coevolution [10.160534429260228]
  我々は、コードでリラックスする学習を通じてNCOPの解像度に革命をもたらす、最初のエンドツーエンドの textbf Automated textbfConst textbfOptimization (AutoCO) 手法を導入する。
  論文  参考訳（メタデータ） (2025-09-16T03:59:51Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.83882149157548]
  大規模言語モデル(LLM)は、アルゴリズム設計を支援する新しい機会を提供する。 LLM4CMOは,2つの人口構成をもつ2段階のフレームワークをベースとした新しいCMOEAである。 LLMは複雑な進化最適化アルゴリズムの開発において効率的な共同設計者として機能する。
  論文  参考訳（メタデータ） (2025-08-16T02:00:57Z)
• From Natural Language to Solver-Ready Power System Optimization: An LLM-Assisted, Validation-in-the-Loop Framework [1.7136832159667206]
  本稿では,Large Language Models (LLMs) を用いたエージェントを導入し,電力系統最適化シナリオの自然言語記述を,コンパクトで解決可能な定式化に自動変換する。 提案手法は,オフザシェルフ最適化解法により効率よく解ける数学的に互換性のある定式化の発見に重点を置いている。
  論文  参考訳（メタデータ） (2025-08-11T16:22:57Z)
• RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs [3.3894236476098185]
  RL-SPHは、非二項整数を含むILPに対しても独立に実現可能な解を生成することができる新しい強化学習ベーススタートプライマーである。 実験により、RL-SPHは、既存の原始よりも平均44倍低い原始ギャップと2.3倍低い積分を達成し、高品質な実現可能な解を迅速に得ることが示された。
  論文  参考訳（メタデータ） (2024-11-29T07:23:34Z)
• LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch [16.174567164068037]
  最適化の一般化を促進するため,LLMOPTと呼ばれる統合学習ベースのフレームワークを提案する。 LLMOPTは、様々な最適化問題タイプを定義するための普遍モデルとして導入された5要素の定式化を構築している。 LLMOPTは線形/非線形プログラミングや混合整数プログラミングといった様々な最適化問題をモデル化することができる。
  論文  参考訳（メタデータ） (2024-10-17T04:37:37Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。 本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。 これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
  論文  参考訳（メタデータ） (2024-03-06T04:43:22Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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