論文の概要: Size Generalization for Diffusion Routing Solvers

• arxiv url: http://arxiv.org/abs/2610.17192v1
• Date: Mon, 12 Oct 2026 17:56:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.433302
• Title: Size Generalization for Diffusion Routing Solvers
• Title（参考訳）: 拡散ルーティング問題に対するサイズ一般化
• Abstract要約: 拡散ベースのソルバは、最適なソリューションセットを使用して教師付き方法でトレーニングし、新しいテストインスタンスを迅速に解決することができる。 しかし、大規模の場合、最適解を見つけることは困難であり、拡散モデルはトレーニング分布外のインスタンスサイズに一般化できない。 本稿では,大規模インスタンスの統計特性の変化に対処するラベル自由サイズ一般化手法であるResizeCOと,それらを迅速に解くための計算課題について述べる。
• 参考スコア（独自算出の注目度）: 37.402948234233286
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.
• Abstract（参考訳）: トラベリングセールスマン問題(TSP)やキャパシタッドカールーティング問題(CVRP)のようなルーティング問題はNPハードであり、大規模インスタンスでは解けない。 拡散ベースのソルバは、最適なソリューションセットを使用して教師付き方法でトレーニングし、新しいテストインスタンスを迅速に解決することができる。 しかし、大規模の場合、最適解を見つけることは困難であり、拡散モデルは訓練分布外のインスタンスサイズに一般化できない。 本稿では,大規模インスタンスの統計特性の変化に対処するラベル自由サイズ一般化手法であるResizeCOについて述べる。 大規模なインスタンス上で強化学習を使用して、小さなインスタンスでトレーニングされた拡散モデルを適用する。 具体的には、経路長をトレーニング信号として用いて、GRPOをこの問題に適応させる。 ResizeCOはまた、k-optをツリーサーチとして定式化し、GPU上のビームサーチによって解決した。 最大10000ノードのTSPおよびCVRPインスタンスにおけるサイズ一般化実験では、ResizeCOは、学習したソルバを支配する経路品質と時間のParetoフロントを達成し、短時間で他のソルバを上回り、新たな最先端技術を確立する。

関連論文リスト

• COMPASS: Ordered Clustered Routing at 100K Scale [58.17379544011152]
  大規模ルーティングは、しばしば所定の順序でノードのクラスタを訪問する必要があるため、順序付きクラスタ旅行セールスマン問題(OCTSP)が発生する。 我々は,並列サブソルバのオーケストレーションによる探索と学習促進ルーティングを組み合わせたOCTSPのCompassアルゴリズムを提案する。 100K合成ノードと28.5K実電子商取引ノードへのスケーリングを実演する。
  論文  参考訳（メタデータ） (2026-09-17T13:17:42Z)
• REVES: REvision and VErification--Augmented Training for Test-Time Scaling [53.197756110943395]
  本稿では,オンラインデータ/プロンプト拡張とポリシー最適化を交互に行う2段階反復フレームワークを提案する。 我々は、RLベースライン上の+6.5点と、標準マルチターントレーニングにおける+4.0点の利得を観察する。
  論文  参考訳（メタデータ） (2026-06-17T10:37:23Z)
• Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application [5.584238928596282]
  カラム生成(CG)は,大規模組合せ最適化(CO)問題における計算効率の向上を目的とした手法である。 資源制約付き最短経路問題(ESPPRC)のサイズ削減にグラフニューラルネットワーク(GNN)を用いる。 削減されたPPは、コストを大幅に削減し収束を高速化するカラムを見つける局所探索によって解決される。
  論文  参考訳（メタデータ） (2025-04-11T10:08:38Z)
• Prompt Learning for Generalized Vehicle Routing [17.424910810870273]
  本研究は, クロスディストリビューション適応のためのニューラル最適化において, 効率的なプロンプト学習手法について検討する。 提案モデルでは, 各種分布の一連のプロンプトを学習し, 最良適合のプロンプトを選択し, 各問題インスタンスに対して事前学習したアテンションモデルを提案する。 また、分散予測とゼロショット一般化の両方において、既存の一般化されたモデルよりも、多様な新しいタスクセットに優れる。
  論文  参考訳（メタデータ） (2024-05-20T15:42:23Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver [15.842155380912002]
  本稿では,ニューラル・ルーティング・ソルバの大規模一般化のための新しいインスタンス・コンディション・アダプタ・モデルを提案する。 提案手法は,非常に高速な推論時間で有望な結果が得られることを示す。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
  車両ルーティング問題 (VRPs) は、幅広い実用化の課題である。 従来あるいは学習ベースの作業は、最大100人の顧客の小さな問題インスタンスに対して、適切なソリューションを実現します。 本稿では,大規模VRPを解くために,新たな局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-08T22:51:58Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。 ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。 実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
  論文  参考訳（メタデータ） (2020-12-19T11:06:30Z)

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

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