論文の概要: 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アプリケーションに取り組む能力を確認している。

関連論文リスト

• Joint Transmit and Pinching Beamforming for PASS: Optimization-Based or Learning-Based? [89.05848771674773]
  MISO (Multiple-input Single-output) フレームワークを提案する。 それは複数の導波路で構成されており、多数の低コストアンテナ(PA)を備えている。 PAの位置は、大規模パスと空間の両方にまたがるように再構成することができる。
  論文  参考訳（メタデータ） (2025-02-12T18:54:10Z)
• PSO and the Traveling Salesman Problem: An Intelligent Optimization Approach [0.0]
  トラベリングセールスマン問題(TSP)は、各都市を正確に1度訪れて出発点に戻る最短ルートを見つけることを目的とした最適化問題である。 本稿では,人口ベース最適化アルゴリズムであるParticle Swarm Optimization (PSO) のTSP解決への応用について検討する。
  論文  参考訳（メタデータ） (2025-01-25T20:21:31Z)
• An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem [21.948190231334088]
  本稿では,トラベリングセールスマン問題に適した効率の良い反復型拡散モデルであるDEITSPを提案する。 本稿では,制御された離散雑音付加プロセスと自己整合性強化を統合した一段階拡散モデルを提案する。 また、ノードとエッジのモダリティから特徴の抽出と融合を促進するために、デュアルモダリティグラフ変換器を設計する。
  論文  参考訳（メタデータ） (2025-01-23T15:47:04Z)
• 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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• 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)
• 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)

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

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