論文の概要: Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application

• arxiv url: http://arxiv.org/abs/2504.08401v1
• Date: Fri, 11 Apr 2025 10:08:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 14:18:14.220309
• Title: Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application
• Title（参考訳）: 列生成における教師なし学習によるグラフの削減:ルーティングアプリケーション
• Authors: Abdo Abouelrous, Laurens Bliea, Adriana F. Gabor, Yaoxin Wu, Yingqian Zhang,
• Abstract要約: カラム生成(CG)は,大規模組合せ最適化(CO)問題における計算効率の向上を目的とした手法である。 資源制約付き最短経路問題(ESPPRC)のサイズ削減にグラフニューラルネットワーク(GNN)を用いる。 削減されたPPは、コストを大幅に削減し収束を高速化するカラムを見つける局所探索によって解決される。
• 参考スコア（独自算出の注目度）: 5.10888539576355
• License:
• Abstract: Column Generation (CG) is a popular method dedicated to enhancing computational efficiency in large scale Combinatorial Optimization (CO) problems. It reduces the number of decision variables in a problem by solving a pricing problem. For many CO problems, the pricing problem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Large ESPPRC instances are difficult to solve to near-optimality. Consequently, we use a Graph neural Network (GNN) to reduces the size of the ESPPRC such that it becomes computationally tractable with standard solving techniques. Our GNN is trained by Unsupervised Learning and outputs a distribution for the arcs to be retained in the reduced PP. The reduced PP is solved by a local search that finds columns with large reduced costs and speeds up convergence. We apply our method on a set of Capacitated Vehicle Routing Problems with Time Windows and show significant improvements in convergence compared to simple reduction techniques from the literature. For a fixed computational budget, we improve the objective values by over 9\% for larger instances. We also analyze the performance of our CG algorithm and test the generalization of our method to different classes of instances than the training data.
• Abstract（参考訳）: コラム生成(CG)は,大規模組合せ最適化(CO)問題における計算効率の向上を目的とした一般的な手法である。 価格問題を解くことで、問題における決定変数の数を減らす。 多くのCO問題に対して、価格問題は資源制約付き最短経路問題(ESPPRC)である。 大規模なESPPRCインスタンスは、ほぼ最適に解決することが難しい。 その結果、グラフニューラルネットワーク(GNN)を用いて、ESPPRCのサイズを削減し、標準解法で計算可能となる。 我々のGNNは教師なし学習(Unsupervised Learning)によって訓練され、削減されたPPに保持される弧の分布を出力する。 削減されたPPは、コストを大幅に削減し収束を高速化するカラムを見つける局所探索によって解決される。 本稿では,時間Windowsを用いたキャパシタント車両ルーティング問題に本手法を適用し,文献からの簡単な低減手法と比較して,コンバージェンスを著しく改善したことを示す。 固定された計算予算では、より大きなインスタンスに対して 9 % 以上の目標値を改善する。 また、CGアルゴリズムの性能を解析し、トレーニングデータと異なるインスタンスのクラスに対する手法の一般化を検証した。

関連論文リスト

• CACTO-SL: Using Sobolev Learning to improve Continuous Actor-Critic with Trajectory Optimization [12.115023915042617]
  トラボ学習ガイドTOと強化学習(RL)は最適な制御問題を解決するための強力なツールである。 本稿では,Solev-SLのアイデアを利用したCACTOの拡張について述べる。
  論文  参考訳（メタデータ） (2023-12-17T09:44:41Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• 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)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Learning to Optimize Non-Rigid Tracking [54.94145312763044]
  我々は、堅牢性を改善し、解法収束を高速化するために学習可能な最適化を採用する。 まず、CNNを通じてエンドツーエンドに学習された深い特徴にアライメントデータ項を統合することにより、追跡対象をアップグレードする。 次に,プレコンディショニング手法と学習手法のギャップを,プレコンディショナを生成するためにトレーニングされたConditionNetを導入することで埋める。
  論文  参考訳（メタデータ） (2020-03-27T04:40:57Z)

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

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