論文の概要: LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning

• arxiv url: http://arxiv.org/abs/2607.28135v1
• Date: Thu, 30 Jul 2026 12:45:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-31 21:37:00.566525
• Title: LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
• Title（参考訳）: LM-GRASP:オンライン模倣学習による組合せ構築のためのインスタンス特化言語モデル
• Abstract要約: 本稿では,GRASPのランダム化構築フェーズをオンライン模倣学習タスクとして再構成するメタヒューリスティックフレームワークを提案する。 ローカルサーチプロシージャが専門のオラクルとして機能し、デコーダのみのトランスフォーマーが建設ポリシーとして機能する。 我々はこれを、反復的な学習-推論-改善サイクルに続くハイブリッドメタヒューリスティック LM-GRASP としてインスタンス化する。
• 参考スコア（独自算出の注目度）: 2.976756502635419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.
• Abstract（参考訳）: 組合せ最適化のための機械学習は、通常、大規模なオフラインデータセットでトレーニングされたニューラルネットワークコンストラクタに頼っている。 本稿では,GRASPのランダム化構築フェーズを,各問題インスタンスのスクラッチから学習したオンライン模倣学習タスクとして再構成するメタヒューリスティックフレームワークを提案する。 ローカルサーチプロシージャが専門のオラクルとして機能し、デコーダのみのトランスフォーマーが建設ポリシーとして機能する。 局所スカラーコストに基づく静的な神秘的ヒューリスティックなルールに依存する従来のGRASPとは異なり,本手法は完全にデータ駆動型である。 我々はこれをLM-GRASPと呼ぶ。これは反復的な学習-推論-改善サイクルに従ってハイブリッドメタヒューリスティックであり、エリートなトラジェクトリの外部データの動的なアーカイブやオフライン事前訓練で行動的クローニングを通じてオンラインにポリシーを訓練する。 パイプラインは、ローカルサーチで使用される客観的評価器を通してのみドメインとインターフェースする。 Taillard PFSPベンチマーク(ta51-ta60)で評価され、半分のオプティマが不明なため最も区別されたブロックであり、LM-GRASPはGPU-GRASPを平均28.4で上回り、GPUアクセラレーション(27.2ユニット)よりも上回っているが、標準偏差が重複している。 これは、例えば、オンライン訓練された言語モデルは、手書きのコンストラクタに代わる有望で実用的な代替品であり、特に古典的なグリーディーな構築に抵抗する風景に向いていることを示唆している。

関連論文リスト

• RING: Retrieval-Internalized Generation for Continual Large-Scale Knowledge Injection [88.56816599695391]
  Retrieval-augmented Generation (RAG)は、事実性を改善すると同時に、サービス時のレイテンシとエンジニアリングオーバーヘッドを追加する。 アーキテクチャとトレーニングの両方にまたがる全体的パラダイムであるRING(Retrieval-Internalized Generation)を提案する。
  論文  参考訳（メタデータ） (2026-08-03T03:00:43Z)
• Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization [40.74618635552097]
  ルーティンググラフのための幾何学的自己教師付き事前学習フレームワークを提案する。 このフレームワークは、ポリシー最適化フェーズの前に堅牢な構造表現を学習する。 提案したモデルでは計算効率が優れており、正確な解法であるConcordeよりも最大2桁のスピードアップを実現している。
  論文  参考訳（メタデータ） (2026-07-31T20:23:21Z)
• Solving Integer Linear Programming with Parallel Tempering [25.230514748331274]
  線形プログラミング(ILP)は、幅広い最適化問題をモデリングするための汎用的なフレームワークとして機能する。 我々は、トレーニングや外部のソルバを使わずに、個別の実行可能な領域を直接探索する、ICPのためのソルバフリーサンプリングベース最適化フレームワークを提案する。 提案手法は,200秒の予算内での4つのタスクのうち2つのタスクにおいて,Gurobiに適合あるいは超越した4つのベンチマークでSCIPを一貫して上回り,学習ベースの手法よりも分散シフトに対してかなり頑健である。
  論文  参考訳（メタデータ） (2026-05-28T05:09:21Z)
• AutoOR: Scalably Post-training LLMs to Autoformalize Operations Research Problems [54.593031581486116]
  本稿では,拡張性のある合成データ生成および強化学習パイプラインであるAutoORについて述べる。 AutoORは、標準最適化フォームから検証済みのトレーニングデータを生成し、RL後トレーニングの報奨信号としてソルバ実行フィードバックを使用する。 我々は、AutoORのような手法がAIによる工業的意思決定を著しく加速できると考えている。
  論文  参考訳（メタデータ） (2026-04-18T03:24:54Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。 本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。 本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
  論文  参考訳（メタデータ） (2026-02-10T14:17:53Z)
• Dynamic Rank Reinforcement Learning for Adaptive Low-Rank Multi-Head Self Attention in Large Language Models [0.0]
  大規模言語モデル(LLM)におけるマルチヘッド自己認識(MHSA)の低ランク分解を適応的に最適化する新しいフレームワークである動的ランク強化学習(DR-RL)を提案する。 DR-RLは、浮動小数点演算(FLOP)を著しく低減しつつ、フルランクアテンションと統計的に等価な下流精度を維持している この研究は、MHSAの適応効率と理論的厳密さのギャップを埋め、リソース制約の深層学習におけるランク低減技術に代えて、原理的に数学的に基礎付けられた代替手段を提供する。
  論文  参考訳（メタデータ） (2025-12-17T21:09:19Z)
• Sample-Efficient Online Learning in LM Agents via Hindsight Trajectory Rewriting [92.57796055887995]
  本稿では,言語モデルエージェントの強化学習から後視体験のリプレイに適応するプロンプトフレームワークECHOを紹介する。 ECHOは失敗した試みで達成できた代替目標のために最適化された軌道を生成する。 我々は、テキストベースのナビゲーションと計画ベンチマークであるXMiniGridのステートフルバージョンと、協調的な情報収集企業シミュレーションであるPeopleJoinQAについて、ECHOを評価した。
  論文  参考訳（メタデータ） (2025-10-11T18:11:09Z)
• CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design [11.639825726501659]
  大規模言語モデル(LLM)は、従来のコストのごく一部で自律的にハイパフォーマンスを発見できる。 本稿では,言語指導と数値指導を組み合わせたハイブリッドフレームワークを提案する。 本手法は,様々な最適化タスクにおいて,SOTA(State-of-the-art)ベースラインを上回っている。
  論文  参考訳（メタデータ） (2025-05-18T07:48:47Z)
• Prompt Optimization via Adversarial In-Context Learning [51.18075178593142]
  adv-ICLは、ジェネレータとディスクリミネータの間の2プレイヤーゲームとして実装される。 ジェネレータは、判別器を騙すのに十分な出力を生成する。 本稿では,Adv-ICLが最先端のプロンプト最適化技術を大幅に改善することを示す。
  論文  参考訳（メタデータ） (2023-12-05T09:44:45Z)
• Integrating LLMs and Decision Transformers for Language Grounded Generative Quality-Diversity [0.0]
  品質多様性(Quality-Diversity)は最適化の一分野であり、強化学習と制御ドメインの問題によく適用される。 本稿では,レパートリーをトラジェクトリの自然言語記述で拡張する大規模言語モデルを提案する。 また、このような生成エージェントの性能を評価するためのLCMベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2023-08-25T10:00:06Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)

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

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