論文の概要: On Statistical Learning of Branch and Bound for Vehicle Routing Optimization

• arxiv url: http://arxiv.org/abs/2310.09986v1
• Date: Sun, 15 Oct 2023 23:59:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-17 17:09:18.231318
• Title: On Statistical Learning of Branch and Bound for Vehicle Routing Optimization
• Title（参考訳）: 車両経路最適化のための分岐境界の統計的学習について
• Authors: Andrew Naguib, Waleed A. Yousef, Issa Traor\'e, Mohammed Mamun
• Abstract要約: 我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。 このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
• 参考スコア（独自算出の注目度）: 3.4300974012019134
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, machine learning of the branch and bound algorithm has shown promise in approximating competent solutions to NP-hard problems. In this paper, we utilize and comprehensively compare the outcomes of three neural networks--graph convolutional neural network (GCNN), GraphSAGE, and graph attention network (GAT)--to solve the capacitated vehicle routing problem. We train these neural networks to emulate the decision-making process of the computationally expensive Strong Branching strategy. The neural networks are trained on six instances with distinct topologies from the CVRPLIB and evaluated on eight additional instances. Moreover, we reduced the minimum number of vehicles required to solve a CVRP instance to a bin-packing problem, which was addressed in a similar manner. Through rigorous experimentation, we found that this approach can match or improve upon the performance of the branch and bound algorithm with the Strong Branching strategy while requiring significantly less computational time. The source code that corresponds to our research findings and methodology is readily accessible and available for reference at the following web address: \href{https://isotlaboratory.github.io/ml4vrp/}{https://isotlaboratory.github.io/ml4vrp/}.
• Abstract（参考訳）: 近年,分枝境界アルゴリズムの機械学習により,np問題に対する有能解の近似が期待されている。 本稿では,3つのニューラルネットワーク – Graph Convolutional Neural Network (GCNN), GraphSAGE, Graph attention Network (GAT) の結果を総合的に比較し,静電容量化車両ルーティング問題を解決する。 計算コストの高いStrong Branching戦略の決定過程をエミュレートするために,これらのニューラルネットワークをトレーニングする。 ニューラルネットワークは、CVRPLIBとは異なるトポロジを持つ6つのインスタンスでトレーニングされ、8つの追加インスタンスで評価される。 さらに,CVRPインスタンスの解決に必要な車両の最小数を,同様の方法で対処したビンパッケージ問題に削減した。 厳密な実験により、この手法は、計算時間を大幅に削減しつつ、Strong Branching戦略と分岐およびバウンドアルゴリズムの性能を一致または改善できることがわかった。 我々の研究成果と方法論に対応するソースコードは、下記のWebアドレスで参照可能である: \href{https://isotlaboratory.github.io/ml4vrp/}{https://isotlaboratory.github.io/ml4vrp/}。

関連論文リスト

• Neural Networks for Vehicle Routing Problem [0.0]
  ルート最適化はニューラルネットワークの新たな課題と見なすことができる。 機械学習の最近の進歩は、複雑な問題に対処するための新しいツールセットを提供する。 ニューラルネットワークを応用する主な領域は、分類と回帰の領域である。
  論文  参考訳（メタデータ） (2024-09-17T15:45:30Z)
• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut [1.4624458429745086]
  本研究は,最適な性能を持つ1つのアルゴリズムを選択するのではなく,インスタンスに基づいてアルゴリズムを選択することが可能となるような設定を考慮し,最近の研究を基礎にしている。 特に、代表的なインスタンスのサンプルが与えられた場合、問題のインスタンスをそのインスタンスの最も適切なアルゴリズムにマッピングするニューラルネットワークを学習する。 言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
  論文  参考訳（メタデータ） (2024-02-04T03:03:27Z)
• Unfolded proximal neural networks for robust image Gaussian denoising [7.018591019975253]
  本稿では,二元FBと二元Chambolle-Pockアルゴリズムの両方に基づいて,ガウス分母タスクのためのPNNを統一的に構築するフレームワークを提案する。 また、これらのアルゴリズムの高速化により、関連するNN層におけるスキップ接続が可能であることを示す。
  論文  参考訳（メタデータ） (2023-08-06T15:32:16Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• A Continuous Optimisation Benchmark Suite from Neural Network Regression [0.0]
  ニューラルネットワークのトレーニングは、近年のディープラーニングの成功で注目を集めている最適化タスクである。 勾配降下変種は、大規模機械学習タスクにおける信頼性の高いパフォーマンスにおいて、最も一般的な選択である。 CORNNは、ニューラルネットワークのトレーニング問題に対して、連続的なブラックボックスアルゴリズムのパフォーマンスをベンチマークするスイートである。
  論文  参考訳（メタデータ） (2021-09-12T20:24:11Z)
• Solve routing problems with a residual edge-graph attention neural network [10.42872026679616]
  本稿では,NP-ハード最適化問題を解決するために,エンドツーエンドの深層強化学習フレームワークを提案する。 提案するフレームワークは、ニューラルネットワークモデルとトレーニングアルゴリズムの観点から、リテラシーのモデルを改善することを目指している。 具体的には、平均最適性ギャップは、100ノードのTSPで4.53%(ベスト citeR22として報告)から3.67%(ベスト citeR22で報告)、100ノードのCVRPで7.34%(ベスト citeR22で報告)から6.68%に縮小される。
  論文  参考訳（メタデータ） (2021-05-06T14:47:47Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  サンプルサブネットワークの性能に適合するグラフ畳み込みネットワークを訓練する。 この戦略により、選択された候補集合において、より高いランク相関係数が得られる。
  論文  参考訳（メタデータ） (2020-04-17T19:12:39Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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