論文の概要: Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problem

• arxiv url: http://arxiv.org/abs/2510.00958v1
• Date: Wed, 01 Oct 2025 14:31:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.611642
• Title: Test-Time Search in Neural Graph Coarsening Procedures for the Capacitated Vehicle Routing Problem
• Title（参考訳）: 静電容量車両ルーティング問題に対するニューラルグラフ粗化法におけるテスト時間探索
• Authors: Yoonju Sim, Hyeonah Kim, Changhyun Kwon,
• Abstract要約: キャパシタ容量不等式(RCIs)のような有効不等式の同定は、キャパシタ付き車両ルーティング問題(CVRP)の切断面法の重要な構成要素である。 深層学習に基づく分離手法では,高品質なカットの発見が可能であるが,多種多様なサブセットを生成できないため,予測よりも少ないカットを生成できることがわかった。 本稿では,新しいテスト時間探索アグリティーを用いて,推論時間における学習モデルの性能を向上させる方法を提案する。
• 参考スコア（独自算出の注目度）: 3.8867154628905767
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The identification of valid inequalities, such as the rounded capacity inequalities (RCIs), is a key component of cutting plane methods for the Capacitated Vehicle Routing Problem (CVRP). While a deep learning-based separation method can learn to find high-quality cuts, our analysis reveals that the model produces fewer cuts than expected because it is insufficiently sensitive to generate a diverse set of generated subsets. This paper proposes an alternative: enhancing the performance of a trained model at inference time through a new test-time search with stochasticity. First, we introduce stochastic edge selection into the graph coarsening procedure, replacing the previously proposed greedy approach. Second, we propose the Graph Coarsening History-based Partitioning (GraphCHiP) algorithm, which leverages coarsening history to identify not only RCIs but also, for the first time, the Framed capacity inequalities (FCIs). Experiments on randomly generated CVRP instances demonstrate the effectiveness of our approach in reducing the dual gap compared to the existing neural separation method. Additionally, our method discovers effective FCIs on a specific instance, despite the challenging nature of identifying such cuts.
• Abstract（参考訳）: ラウンドドキャパシティの不等式(RCIs)のような有効な不等式を特定することは、キャパシタント・ビークル・ルーティング問題(CVRP)におけるカットプレーン法の重要な構成要素である。 深層学習に基づく分離手法では,高品質なカットの発見が可能であるが,多種多様なサブセットを生成するには十分ではないため,予測よりも少ないカットを生成できることがわかった。 本稿では,確率性のある新しいテスト時間探索により,推論時間における学習モデルの性能を向上させる方法を提案する。 まず,グラフ粗化手法に確率的エッジ選択を導入し,従来提案されていた欲求的アプローチを置き換える。 第2に、粗大化履歴を利用したグラフ粗大化履歴分割法(GraphCHiP)を提案する。 ランダムに生成されたCVRPインスタンスの実験は、既存の神経分離法と比較して二重ギャップを低減する方法の有効性を示した。 さらに,本手法は,そのような切断を識別する難しい性質にもかかわらず,特定の事例において有効なFCIを検出する。

関連論文リスト

• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。 本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。 低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
  論文  参考訳（メタデータ） (2022-11-03T16:42:40Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  本稿では、分散正規化損失最小化問題に対する2倍加速勾配降下法(ADSGD)を提案する。 まず、ADSGDが線形収束率を達成でき、全体的な計算複雑性を低減できることを示す。
  論文  参考訳（メタデータ） (2022-08-11T22:27:22Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  次世代のスケーラブル因果発見手法の設計方法について述べる。 本稿では,スコアのヤコビアンを効率的に近似し,因果グラフを復元する手法を提案する。
  論文  参考訳（メタデータ） (2022-03-08T21:34:46Z)
• Unsupervised feature selection via self-paced learning and low-redundant regularization [6.083524716031565]
  自己評価学習とサブスペース学習の枠組みを統合することにより,教師なしの特徴選択を提案する。 この手法の収束性は理論的および実験的に証明される。 実験の結果,提案手法はクラスタリング法の性能を向上し,他の比較アルゴリズムよりも優れていることがわかった。
  論文  参考訳（メタデータ） (2021-12-14T08:28:19Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  本稿では,実効的かつ理論的に証明可能なアルゴリズムであるオフラインRLに対するfalSe Correlation Reduction (SCORE)を提案する。 SCOREは、標準ベンチマーク(D4RL)において、様々なタスクにおいて3.1倍の高速化でSoTA性能を達成することを実証的に示す。
  論文  参考訳（メタデータ） (2021-10-24T15:34:03Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic [5.395127324484869]
  SplitSGDは最適化のための新しい動的学習スケジュールである。 本手法は,対象関数の局所的幾何への適応性を向上するために学習率を低下させる。 基本的には標準のSGDよりも計算コストがかかるわけではない。
  論文  参考訳（メタデータ） (2019-10-18T19:38:53Z)

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

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