論文の概要: R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling

• arxiv url: http://arxiv.org/abs/2508.15204v1
• Date: Thu, 21 Aug 2025 03:35:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-22 16:26:46.165937
• Title: R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling
• Title（参考訳）: R-ConstraintBench:NP-Complete スケジューリングにおける LLM の評価
• Authors: Raj Jain, Marc Wetter,
• Abstract要約: R-ConstraintBenchは、資源制約計画スケジューリング問題(RCPSP)のモデルを評価するフレームワークである。 データセンターのマイグレーション設定でベンチマークをインスタンス化し、実行可能性とエラー分析を用いて複数のLCMを評価する。 実証的には、強いモデルは優先順位のみのDAGでほぼシーリングされるが、ダウンタイム、時間的ウィンドウ、および解離的制約が相互作用すると、実現可能性のパフォーマンスは低下する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Effective scheduling under tight resource, timing, and operational constraints underpins large-scale planning across sectors such as capital projects, manufacturing, logistics, and IT fleet transitions. However, the reliability of large language models (LLMs) when reasoning under high-constraint regimes is insufficiently characterized. To address this gap, we present R-ConstraintBench, a scalable framework that evaluates models on Resource-Constrained Project Scheduling Problems (RCPSP), an NP-Complete feasibility class, while difficulty increases via linear growth in constraints. R-ConstraintBench incrementally increases non-redundant precedence constraints in Directed Acyclic Graphs (DAGs) and then introduces downtime, temporal windows, and disjunctive constraints. As an illustrative example, we instantiate the benchmark in a data center migration setting and evaluate multiple LLMs using feasibility and error analysis, identifying degradation thresholds and constraint types most associated with failure. Empirically, strong models are near-ceiling on precedence-only DAGs, but feasibility performance collapses when downtime, temporal windows, and disjunctive constraints interact, implicating constraint interaction, not graph depth, as the principal bottleneck. Performance on clean synthetic ramps also does not guarantee transfer to domain-grounded scenarios, underscoring limited generalization.
• Abstract（参考訳）: 厳格な資源、タイミング、運用上の制約の下での効果的なスケジューリングは、資本プロジェクト、製造、物流、ITフラッグシップの移行といった分野にわたる大規模な計画を支えている。 しかし,高制約条件下での推論における言語モデル(LLM)の信頼性は不十分である。 本稿では,資源制約付きプロジェクトスケジューリング問題 (RCPSP) のモデルを評価するスケーラブルなフレームワークであるR-ConstraintBenchについて述べる。 R-ConstraintBenchは、DAG(Directed Acyclic Graphs)における非冗長優先制約を漸進的に増加させ、ダウンタイム、時間ウィンドウ、および解離制約を導入する。 実証的な例として、データセンターのマイグレーション設定でベンチマークをインスタンス化し、実行可能性とエラー分析を用いて複数のLCMを評価し、故障に最も関係のある劣化しきい値と制約タイプを特定します。 実証的に言えば、強いモデルは最優先のDAGに近づきつつあるが、ダウンタイム、時間的ウィンドウ、および解離的制約が相互作用し、グラフの深さではなく制約の相互作用を主要なボトルネックとして含み、実現可能性のパフォーマンスは崩壊する。 クリーンな合成ランプの性能は、限定的な一般化を前提に、ドメイン基底のシナリオへの転送を保証しない。

関連論文リスト

• CSGO: Generalized Optimization for Cold Start in Wireless Collaborative Edge LLM Systems [62.24576366776727]
  本稿では,全体の推論遅延を最小限に抑えるために,遅延を考慮したスケジューリングフレームワークを提案する。 提案手法は,ベースライン戦略と比較して,コールドスタート遅延を著しく低減することを示す。
  論文  参考訳（メタデータ） (2025-08-15T07:49:22Z)
• TCP: a Benchmark for Temporal Constraint-Based Planning [8.977867314314386]
  時間的推論と計画は、大きな言語モデルにとって不可欠な機能である。 両機能を共同で評価する,時間制約に基づく計画ベンチマークを導入する。 我々は、最先端のLCMを評価し、最強のモデルでさえTCPに苦しむことを発見した。
  論文  参考訳（メタデータ） (2025-05-26T12:53:01Z)
• Scalable Chain of Thoughts via Elastic Reasoning [61.75753924952059]
  Elastic Reasoningは、スケーラブルな思考の連鎖のための新しいフレームワークである。 推論は、独立して割り当てられた予算で、思考と解決の2つのフェーズに分けられる。 我々のアプローチは、制約のない設定でもより簡潔で効率的な推論をもたらす。
  論文  参考訳（メタデータ） (2025-05-08T15:01:06Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  本稿では,現実の調理シナリオに基づいた新しいベンチマークフレームワークRecipe2Planを紹介する。 従来のベンチマークとは異なり、Recipe2Planは並列タスク実行による調理時間を最適化するためにエージェントに挑戦する。
  論文  参考訳（メタデータ） (2025-03-04T03:27:02Z)
• Semantic Integrity Constraints: Declarative Guardrails for AI-Augmented Data Processing Systems [39.23499993745249]
  セマンティッククエリにおけるLLM出力に対する正当性条件を指定・強制するためのセマンティック整合性制約(SIC)を導入する。 SICは、従来のデータベース整合性制約をセマンティックセッティングに一般化し、グラウンド、サウンドネス、排他といった一般的なタイプの制約をサポートする。 本稿では,SICをクエリ計画と実行環境に統合するシステム設計について述べる。
  論文  参考訳（メタデータ） (2025-03-01T19:59:25Z)
• Deep Neural Network for Constraint Acquisition through Tailored Loss Function [0.0]
  データから制約を学習することの重要性は、実世界の問題解決における潜在的な応用によって裏付けられている。 この研究は、シンボリック回帰に基づくディープニューラルネットワーク(DNN)に基づく新しいアプローチを導入する。
  論文  参考訳（メタデータ） (2024-03-04T13:47:33Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  本稿では、新しいアルゴリズムを用いて、弱監督(GLWS)から学習するための一般的な枠組みを紹介する。 GLWSの中心は期待最大化(EM)の定式化であり、様々な弱い監督源を順応的に収容している。 また,EM計算要求を大幅に単純化する高度なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T21:48:50Z)
• Generating Dispatching Rules for the Interrupting Swap-Allowed Blocking Job Shop Problem Using Graph Neural Network and Reinforcement Learning [21.021840570685264]
  割り込みスワップ可能なブロッキングジョブショップ問題(ISBJSSP)は、多くの製造計画やロジスティクスアプリケーションを現実的にモデル化することができる。 連続的な削除や加算を受けるノードとエッジを特徴とする動的解離グラフの定式化を導入する。 ISBJSSP設定の割り込み、スワップ、ブロッキングをシミュレートするシミュレータが開発された。
  論文  参考訳（メタデータ） (2023-02-05T23:35:21Z)
• Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization [1.662966122370634]
  オンライン凸最適化(OCO)と時間的損失と制約関数について検討する。 まず,時間変動関数制約OCOのためのモデルベース拡張ラグランジアン法(MALM)のクラスを開発する。 提案アルゴリズムの効率性を示すために, 制約OCOのいくつかの例について数値計算を行った。
  論文  参考訳（メタデータ） (2022-05-19T14:03:25Z)

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

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