論文の概要: A Neural Separation Algorithm for the Rounded Capacity Inequalities

• arxiv url: http://arxiv.org/abs/2306.17283v2
• Date: Sat, 28 Oct 2023 07:11:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-31 21:01:55.761959
• Title: A Neural Separation Algorithm for the Rounded Capacity Inequalities
• Title（参考訳）: 丸い容量の不等式に対するニューラルネットワーク分離アルゴリズム
• Authors: Hyeonah Kim and Jinkyoo Park and Changhyun Kwon
• Abstract要約: グラフニューラルネットワーク(GNN)による正確な問題の解を学習するグラフ粗化を用いた学習ベース分離アルゴリズムを設計する。 CVRPSEPは,VRPの解決に使用される様々なカットのための,一般的な分離ソフトウェアパッケージである。
• 参考スコア（独自算出の注目度）: 19.31854552060491
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The cutting plane method is a key technique for successful branch-and-cut and branch-price-and-cut algorithms that find the exact optimal solutions for various vehicle routing problems (VRPs). Among various cuts, the rounded capacity inequalities (RCIs) are the most fundamental. To generate RCIs, we need to solve the separation problem, whose exact solution takes a long time to obtain; therefore, heuristic methods are widely used. We design a learning-based separation heuristic algorithm with graph coarsening that learns the solutions of the exact separation problem with a graph neural network (GNN), which is trained with small instances of 50 to 100 customers. We embed our separation algorithm within the cutting plane method to find a lower bound for the capacitated VRP (CVRP) with up to 1,000 customers. We compare the performance of our approach with CVRPSEP, a popular separation software package for various cuts used in solving VRPs. Our computational results show that our approach finds better lower bounds than CVRPSEP for large-scale problems with 400 or more customers, while CVRPSEP shows strong competency for problems with less than 400 customers.
• Abstract（参考訳）: 切削平面法は、様々な車両経路問題(vrps)の最適解を求める分岐・切削・分岐価格・切削アルゴリズムを成功させる鍵となる手法である。 様々なカットのうち、丸い容量の不等式(rcis)が最も基本的なものである。 rcisを生成するには、正確な解を得るのに時間がかかる分離問題を解く必要があるため、ヒューリスティックな手法が広く使われている。 グラフニューラルネットワーク(gnn)を用いて,厳密な分離問題の解法を学習するグラフ粗粒化を用いた,学習に基づく分離ヒューリスティックアルゴリズムを設計した。 分離アルゴリズムを切断平面法に組み込んで,最大1,000人の顧客を抱えた静電容量VRP(CVRP)の低いバウンドを求める。 CVRPSEPは,VRPの解決に使用される様々なカットのための,一般的な分離ソフトウェアパッケージである。 計算結果から,CVRPSEPは400人以上の顧客を抱える大規模問題に対して,CVRPSEPよりも低い限界が得られ,CVRPSEPは400人未満の問題に対して高い能力を示した。

関連論文リスト

• Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness [0.0]
  単一パススケジューリングアルゴリズムで用いられる基準値の分解時間推定器として機能するディープニューラルネットワークを提案する。 機械学習によるアプローチは、トレーニングフェーズからかなり大きなインスタンスへの情報を効率的に一般化できることを示します。
  論文  参考訳（メタデータ） (2024-02-19T15:34:09Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
  論文  参考訳（メタデータ） (2024-01-20T06:06:01Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27: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)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
  車両ルーティング問題 (VRPs) は、幅広い実用化の課題である。 従来あるいは学習ベースの作業は、最大100人の顧客の小さな問題インスタンスに対して、適切なソリューションを実現します。 本稿では,大規模VRPを解くために,新たな局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-08T22:51:58Z)
• 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)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)

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

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