論文の概要: On Statistical Learning of Branch and Bound for Vehicle Routing
Optimization
- arxiv url: http://arxiv.org/abs/2310.09986v2
- Date: Tue, 17 Oct 2023 17:50:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 11:00:45.840235
- Title: On Statistical Learning of Branch and Bound for Vehicle Routing
Optimization
- Title(参考訳): 車両経路最適化のための分岐境界の統計的学習について
- Authors: Andrew Naguib, Waleed A. Yousef, Issa Traor\'e, Mohammad Mamun
- Abstract要約: 我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。
このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
- 参考スコア(独自算出の注目度): 3.6922704509753084
- 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: 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アドレスで参照することができる。
関連論文リスト
- Data-driven algorithm design using neural networks with applications to
branch-and-cut [1.597617022056624]
我々は、この研究の行において、最高のパフォーマンスを持つ1つのアルゴリズムを選択する代わりに、そのインスタンスに基づいてアルゴリズムを選択することができるというアイデアを導入することによって、最近の研究の上に構築する。
我々は、このアイデアを形式化し、データ駆動アルゴリズム設計における最近の研究の精神の中で、この学習問題に対する厳密なサンプル複雑性を導出する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
論文 参考訳(メタデータ) (2024-02-04T03:03:27Z) - PNN: From proximal algorithms to robust unfolded image denoising
networks and Plug-and-Play methods [7.317910352447519]
本稿では,二元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) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
論文 参考訳(メタデータ) (2022-07-30T12:34:26Z) - 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) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳(メタデータ) (2020-05-05T18:08:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。