論文の概要: DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2501.08565v1
• Date: Wed, 15 Jan 2025 04:16:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:52:38.045013
• Title: DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem
• Title（参考訳）: DualOpt: 大規模旅行セールスマン問題に対する二分割最適化アルゴリズム
• Authors: Shipei Zhou, Yuandong Ding, Chi Zhang, Zhiguang Cao, Yan Jin,
• Abstract要約: 大規模旅行セールスマン問題(T)を解決するための二分割最適化アルゴリズム(DualOpt)を提案する。 DualOptは、ソリューションの品質と計算効率の両方を改善するための2つの補完戦略を組み合わせる。 提案したDualOptは、文学における10の最先端アルゴリズムと比較して非常に競争力のある結果が得られる。
• 参考スコア（独自算出の注目度）: 16.841700899374654
• License:
• Abstract: This paper proposes a dual divide-and-optimize algorithm (DualOpt) for solving the large-scale traveling salesman problem (TSP). DualOpt combines two complementary strategies to improve both solution quality and computational efficiency. The first strategy is a grid-based divide-and-conquer procedure that partitions the TSP into smaller sub-problems, solving them in parallel and iteratively refining the solution by merging nodes and partial routes. The process continues until only one grid remains, yielding a high-quality initial solution. The second strategy involves a path-based divide-and-optimize procedure that further optimizes the solution by dividing it into sub-paths, optimizing each using a neural solver, and merging them back to progressively improve the overall solution. Extensive experiments conducted on two groups of TSP benchmark instances, including randomly generated instances with up to 100,000 nodes and real-world datasets from TSPLIB, demonstrate the effectiveness of DualOpt. The proposed DualOpt achieves highly competitive results compared to 10 state-of-the-art algorithms in the literature. In particular, DualOpt achieves an improvement gap up to 1.40% for the largest instance TSP100K with a remarkable 104x speed-up over the leading heuristic solver LKH3. Additionally, DualOpt demonstrates strong generalization on TSPLIB benchmarks, confirming its capability to tackle diverse real-world TSP applications.
• Abstract（参考訳）: 本稿では、大規模旅行セールスマン問題(TSP)を解決するための二分割最適化アルゴリズム(DualOpt)を提案する。 DualOptは、ソリューションの品質と計算効率の両方を改善するための2つの補完戦略を組み合わせる。 第1の戦略はグリッドベースの分割処理であり、TSPを小さなサブプロブレムに分割し、それらを並列に解決し、ノードと部分ルートをマージしてソリューションを反復的に洗練する。 プロセスは1つのグリッドのみが残るまで続き、高品質な初期解が得られる。 第2の戦略は、パスベースの分割最適化手順で、サブパスに分割し、ニューラルソルバを使用してそれぞれを最適化し、それらをマージして、全体的なソリューションを段階的に改善することで、ソリューションをさらに最適化する。 最大10万のノードを持つランダムに生成されたインスタンスと、TSPLIBの実際のデータセットを含む、TSPベンチマークインスタンスの2つのグループで実施された大規模な実験は、DualOptの有効性を実証している。 提案したDualOptは、文学における10の最先端アルゴリズムと比較して非常に競争力のある結果が得られる。 特に、DualOptは、最大のTSP100Kに対して最大1.40%の改善ギャップを達成し、主要なヒューリスティックソルバLKH3よりも104倍のスピードアップを実現している。 さらに、DualOptはTSPLIBベンチマークの強力な一般化を示し、様々な現実世界のTSPアプリケーションに取り組む能力を確認している。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Stabilized Proximal-Point Methods for Federated Optimization [20.30761752651984]
  非加速アルゴリズムの通信複雑性は、分散近位点アルゴリズムであるDANEによって達成される。 ハイブリッド投影近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。 S-DANEは、S-DANEとして良好な局所計算効率を保ちながら、通信の複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2024-07-09T17:56:29Z)
• Toward Rapid, Optimal, and Feasible Power Dispatch through Generalized Neural Mapping [0.0]
  パワーディスパッチ問題を解決するための学習ベースアプローチとして LOOP-LC 2.0 を提案する。 LOOP-LC 2.0フレームワークの顕著な利点は、ソリューションのほぼ最適性と厳密な実現性を保証する能力である。 本稿では, LOOP-LC 2.0法の有効性を, 学習速度, 計算時間, 最適性, ソリューション実現可能性の観点から示す。
  論文  参考訳（メタデータ） (2023-11-08T17:02:53Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
  直交制約付き分散最適化のための新しいアルゴリズムを提案する。 VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。 数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
  論文  参考訳（メタデータ） (2022-08-29T14:46:44Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations [27.353023427198806]
  我々は、制約のない最適化問題(POP)の高次半定値プログラミング緩和を考察する。 POPから独立してSDPを解く既存のアプローチは、そのようなSDPの典型的な非エネルギー性のため、大きな問題にスケールできないか、あるいは緩やかな収束に苦しむことができない。 我々は SpecTrahedral vErtices (STRIDE) と呼ばれる新しいアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-05-28T18:07:16Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。 本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-27T17:38:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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