論文の概要: Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

• arxiv url: http://arxiv.org/abs/2603.23290v1
• Date: Tue, 24 Mar 2026 14:54:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-25 19:53:37.544513
• Title: Traveling Salesman Problem with a preprocessing method for classical and quantum optimization
• Title（参考訳）: 古典的および量子最適化のための前処理法によるトラベリングセールスマン問題
• Authors: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero,
• Abstract要約: トラベリングセールスマン問題(Traveing Salesman Problem)は、オペレーション研究において広く研究されている基本的な最適化問題である。 単純な定式化にもかかわらず、探索空間の指数的な成長と多くの制約のために計算的に困難である。 本稿では,最適化モデルのサイズを大幅に削減する前処理戦略を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Traveling Salesman Problem is a fundamental combinatorial optimization problem widely studied in operations research. Despite its simple formulation, it remains computationally challenging due to the exponential growth of the search space and the large number of constraints required to eliminate subtours. This paper introduces a preprocessing strategy that significantly reduces the size of the optimization model by restricting the set of candidate arcs and retaining only the lowest-cost neighbors for each vertex. Computational experiments on TSPLIB benchmark instances demonstrate that the proposed approach substantially reduces the number of decision variables. The method is evaluated using both classical and quantum optimization techniques, showing improvements in computational time and reductions in optimality gaps. Overall, the results indicate that the proposed preprocessing enhances the scalability of the formulations and makes them more suitable for both classical solvers and emerging quantum optimization frameworks.
• Abstract（参考訳）: トラベリングセールスマン問題(Traveing Salesman Problem)は、オペレーション研究において広く研究されている基本的な組合せ最適化問題である。 単純な定式化にもかかわらず、探索空間の指数関数的な成長と、部分曲線の除去に必要な多くの制約のため、計算的に困難である。 本稿では,候補弧の集合を制限し,各頂点に対して最低コストの隣接点のみを保持することにより,最適化モデルのサイズを大幅に削減する前処理戦略を提案する。 TSPLIBベンチマークインスタンス上での計算実験により,提案手法が決定変数数を著しく減少させることを示した。 この手法は古典的および量子的最適化手法の両方を用いて評価され、計算時間の改善と最適性ギャップの低減を示す。 以上の結果から,提案したプリプロセッシングにより,定式化のスケーラビリティが向上し,古典的解法と量子最適化フレームワークに適合することが示唆された。

関連論文リスト

• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  拡張ラグランジアンに基づくmin-max問題のスムーズな変種を提案する。 提案アルゴリズムは, 段階的戦略よりも目的数で拡張性が高い。
  論文  参考訳（メタデータ） (2025-03-16T11:05:51Z)
• A Simplification Method for Inequality Constraints in Integer Binary Encoding HOBO Formulations [0.0]
  提案手法は,擬似非拘束バイナリ最適化(QUBO)の定式化に伴う課題に対処する。 制約を効率的に統合することにより、量子および古典的解法の計算効率と精度を高めることができる。
  論文  参考訳（メタデータ） (2025-01-16T17:06:25Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• A coherent approach to quantum-classical optimization [0.0]
  ハイブリッド量子古典最適化技術は、量子計算資源の削減を可能にすることが示されている。 我々は、コヒーレンスエントロピーを量子状態の適合性を決定する重要な指標とみなす。 本稿では,従来の課題に対するアプローチを大幅に改善する量子古典最適化プロトコルを提案する。
  論文  参考訳（メタデータ） (2024-09-20T22:22:53Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。 本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
  論文  参考訳（メタデータ） (2024-09-07T19:52:14Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm [0.39945675027960637]
  最適化問題の解法における量子近似最適化アルゴリズム(QAOA)の能力は近年,盛んに研究されている。 本稿では,QAOAによる問題解決における最適化コスト削減の可能性を検討する。
  論文  参考訳（メタデータ） (2023-09-24T05:12:48Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)

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

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