論文の概要: A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

• arxiv url: http://arxiv.org/abs/2403.04917v2
• Date: Mon, 11 Mar 2024 03:47:04 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 13:19:31.408844
• Title: A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
• Title（参考訳）: 凸集合のグラフに基づく移動目標走行セールスマン問題に対する混合整数型conicプログラム
• Authors: Allen George Philip, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset
• Abstract要約: 本稿では,移動目標トラベリングセールスマン問題(MT-TSP)の最適解を求める新しい定式化を提案する。 問題は、補給所から始まるエージェントの最も短い経路を見つけ、割り当てられた時間ウィンドウ内で1度だけ移動対象のセットを訪れ、補給所に戻ることである。 MT-TSPのためのMICP(Mixed Conic Program)の定式化について検討した。
• 参考スコア（独自算出の注目度）: 30.186830876548147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art Mixed Integer Conic Program (MICP) solver for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60\% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower bounds for the MT-TSP than the ones from the MICP.
• Abstract（参考訳）: 本稿では,移動目標トラベリングセールスマン問題 (MT-TSP) の最適解を求める新たな定式化を提案する。 定式化は、目標が直線に沿って移動するとき、その軌道は時空座標系内の凸集合となるというキーアイデアに依存している。 問題は凸集合のグラフ内で最短経路を見つけることとなり、いくつかの速度制約が課される。 我々は,mt-tsp の現在の混合整数 conic プログラム (micp) 法との比較を行った。 実験結果から,提案手法は最大20のターゲット,最大2桁のランタイム削減,最大60\%の最適化ギャップを持つインスタンスに対して,micpよりも優れることがわかった。 また, この定式化の凸緩和による解コストは, MICP の解よりもMT-TSP の解コストがかなり低いことを示す。

関連論文リスト

• Dataless Quadratic Neural Networks for the Maximum Independent Set Problem [23.643727259409744]
  pCQO-MISはエッジ数ではなくグラフ内のノード数でスケールすることを示す。 提案手法は,分散の排除,サンプリング,データ中心のアプローチを回避する。
  論文  参考訳（メタデータ） (2024-06-27T21:12:48Z)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
  本研究では,SPAREを提案する。SPAREは,非剛性登録のための対称化点-平面間距離を用いた新しい定式化である。 提案手法は, 厳密でない登録問題の精度を大幅に向上し, 比較的高い解効率を維持する。
  論文  参考訳（メタデータ） (2024-05-30T15:55:04Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• The Parameterized Complexity of Coordinated Motion Planning [28.39902924923273]
  コーディネート・モーション・プランニング(CMP)では、$k$ロボットが異なるスタート・グリッドポイントを$k$で占有し、異なる目的地・グリッドポイントに$k$で到達する必要がある。 目標は、目標目標を最小限に抑えるために、$k$のロボットを目的地に移動するためのスケジュールを計算することだ。 本稿では,CMP-MとCMP-Lのパラメータ化複雑性を2つの基本パラメータについて検討する。
  論文  参考訳（メタデータ） (2023-12-12T10:26:01Z)
• Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning [4.521119623956821]
  混合整数線形二段階プログラムの解を高速化する手法を提案する。 我々は,第2段階の要求の高い問題を解決することを目的としている。 私たちの中核となる考え方は、オンラインソリューションの時間を大幅に削減し、第一段階ソリューションの精度を小さくすることです。
  論文  参考訳（メタデータ） (2022-05-02T13:15:32Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)

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

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