論文の概要: Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2602.02188v1
• Date: Mon, 02 Feb 2026 14:55:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:34.23177
• Title: Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization
• Title（参考訳）: コンビネーションと制約のある世界での推論:自然言語コンビネーション最適化におけるLLMのベンチマーク
• Authors: Xia Jiang, Jing Chen, Cong Zhang, Jie Gao, Chengpeng Hu, Chenhao Zhang, Yaoxin Wu, Yingqian Zhang,
• Abstract要約: 大規模言語モデル (LLM) は数学や論理的推論において高い性能を示している。 しかし、体系的最適化(CO)を扱う能力はまだ未定である。 エンド・ツー・エンドのCO推論でLLMを評価するベンチマークであるNLCOを紹介する。
• 参考スコア（独自算出の注目度）: 28.52469449694436
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: While large language models (LLMs) have shown strong performance in math and logic reasoning, their ability to handle combinatorial optimization (CO) -- searching high-dimensional solution spaces under hard constraints -- remains underexplored. To bridge the gap, we introduce NLCO, a \textbf{N}atural \textbf{L}anguage \textbf{C}ombinatorial \textbf{O}ptimization benchmark that evaluates LLMs on end-to-end CO reasoning: given a language-described decision-making scenario, the model must output a discrete solution without writing code or calling external solvers. NLCO covers 43 CO problems and is organized using a four-layer taxonomy of variable types, constraint families, global patterns, and objective classes, enabling fine-grained evaluation. We provide solver-annotated solutions and comprehensively evaluate LLMs by feasibility, solution optimality, and reasoning efficiency. Experiments across a wide range of modern LLMs show that high-performing models achieve strong feasibility and solution quality on small instances, but both degrade as instance size grows, even if more tokens are used for reasoning. We also observe systematic effects across the taxonomy: set-based tasks are relatively easy, whereas graph-structured problems and bottleneck objectives lead to more frequent failures.
• Abstract（参考訳）: 大規模言語モデル(LLM)は数学や論理的推論において高い性能を示しているが、組合せ最適化(CO)を扱う能力 -- 厳密な制約の下で高次元の解空間を探索する能力はいまだ検討されていない。 このギャップを埋めるために、NLCO, a \textbf{N}atural \textbf{L}anguage \textbf{C}ombinatorial \textbf{O}ptimization benchmarkを導入します。 NLCOは43のCO問題をカバーし、可変型、制約族、グローバルパターン、目的クラスの4層分類を用いて組織化され、きめ細かい評価を可能にしている。 本稿では,LLMの可視性,解の最適性,推論効率を総合的に評価する。 様々な近代LCMの実験により、高性能モデルが小さなインスタンス上で強力な実現可能性とソリューションの品質を達成することが示されたが、どちらもインスタンスサイズが大きくなるにつれて、推論により多くのトークンが使われるようになる。 セットベースのタスクは比較的容易であるのに対して、グラフ構造化の問題とボトルネックの目的は、より頻繁な失敗につながる。

関連論文リスト

• Multi-Objective Hierarchical Optimization with Large Language Models [41.41567058185742]
  大規模言語モデル(LLM)は、多目的最適化を推進するための既定の選択肢ではない。 本稿では,このギャップを,構造化階層型探索戦略内での代理モデルと候補サンプルとしてLLMを活用することで解決する。
  論文  参考訳（メタデータ） (2026-01-20T12:10:13Z)
• DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization [40.88623618289683]
  大規模言語モデル(LLM)は、最近、プロンプトベースの戦略を通じて最適化問題(COP)に取り組むことを約束している。 メタヒューリスティック設計とLLM推論の長所を組み合わせたDRAGONを提案する。 最適化環境と継続的に対話し、適応的なエクスペリエンスメモリを活用することで、エージェントはフィードバックから反復的に学習する。
  論文  参考訳（メタデータ） (2026-01-10T09:31:40Z)
• Large Language Models as End-to-end Combinatorial Optimization Solvers [45.32050615257007]
  物流や製造などの意思決定シナリオの中心となる組合せ最適化(CO)問題は、伝統的に問題固有のアルゴリズムを使用して解決される。 既存のアプローチは、コード生成やソルバ呼び出しといった中間ステップに依存しており、その汎用性とアクセシビリティを制限している。 本稿では,大規模言語モデル(LLM)を,自然言語問題記述をソリューションに直接マッピングすることで,エンドツーエンドのCOソルバとして機能させる,新たなフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-09-21T01:30:30Z)
• Reasoning with Preference Constraints: A Benchmark for Language Models in Many-to-One Matching Markets [13.111181135818184]
  大規模言語モデル (LLM) は、最適化を含む複雑な数学的タスクにおいて強い性能を示している。 優先的かつ構造的な制約の下で推論を必要とする問題にLLMを適用することは、まだ未定である。 我々は,大学入学問題の369件の新たなベンチマークを用いて,実用性,安定性,最適性といった重要な次元にわたるLSMを評価する。
  論文  参考訳（メタデータ） (2025-09-16T14:48:46Z)
• 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)
• CrossWordBench: Evaluating the Reasoning Capabilities of LLMs and LVLMs with Controllable Puzzle Generation [53.452699232071495]
  そこで我々は,大言語モデル(LLM)とLVLM(Large Vision-Language Model)の推論能力を評価するためのベンチマークであるCrossWordBenchを紹介する。 評価の結果,LLMの推論は,クロスレター制約を効果的に活用することにより,非推論モデルよりも大幅に優れていることがわかった。 本研究は,現在のLLMとLVLMの推論能力の限界を強調し,今後の評価のために,マルチモーダル制約タスクを作成するための効果的なアプローチを提供する。
  論文  参考訳（メタデータ） (2025-03-30T20:03:36Z)
• NPHardEval4V: Dynamic Evaluation of Large Vision-Language Models with Effects of Vision [64.83085920775316]
  NPHardEval4Vは4つの古典的NPハード問題に基づくマルチモーダルベンチマークスイートである。 各タスクは、構造化された視覚レイアウトとテキストプロンプトを組み合わせることで、視覚言語的制約の下で推論を行うLVLMの能力を評価するように設計されている。 以上の結果から,これらのモデルは知覚に基づく入力に対して合理的に優れているが,グローバルな最適化,抽象化,制約満足度に苦慮していることが明らかとなった。
  論文  参考訳（メタデータ） (2024-03-04T07:10:31Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)

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

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