Fugu-MT 論文翻訳(概要): GPS: A new TSP formulation for its generalizations type QUBO

論文の概要: GPS: A new TSP formulation for its generalizations type QUBO

arxiv url: http://arxiv.org/abs/2110.12158v3
Date: Tue, 18 Jan 2022 19:18:08 GMT
ステータス: 処理完了
システム内更新日: 2023-03-10 17:32:46.067376
Title: GPS: A new TSP formulation for its generalizations type QUBO
Title（参考訳）: gps: 一般化型quboのための新しいtsp定式化
Authors: Sa\'ul Gonz\'alez-Bermejo, Guillermo Alonso-Linaje, Parfait Atchade-Adelomou
Abstract要約: 旅行セールスマン問題(TSP)の新しい2次非拘束バイナリ最適化(QUBO)を提案する。必要な変数の最小数の観点から、車両ルーティング問題(VRP)の最良の定式化を克服する。最後に,QUBO問題解法に入力することで定式化の正しさを検証した。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We propose a new Quadratic Unconstrained Binary Optimization (QUBO) formulation of the Travelling Salesman Problem (TSP), with which we overcame the best formulation of the Vehicle Routing Problem (VRP) in terms of the minimum number of necessary variables. After, we present a detailed study of the constraints subject to the new TSP model and benchmark it with MTZ and native formulations. Finally, we tested whether the correctness of the formulation by entering it into a QUBO problem solver. The solver chosen is a D-Wave\_2000Q6 quantum computer simulator due to the connection between Quantum Annealing and QUBO formulations.
Abstract（参考訳）: 本稿では, 走行販売マン問題 (TSP) の2次非拘束二元最適化 (QUBO) の定式化を提案し, 必要な変数の最小数の観点から, 車両ルーティング問題 (VRP) の最適定式化を克服する。その後,新しいtspモデルに基づく制約の詳細な研究を行い,mtzおよびネイティブな定式化を用いてベンチマークを行う。最後に,QUBO問題解法に入力することで定式化の正しさを検証した。 D-Wave\_2000Q6量子コンピュータシミュレータは量子アニーリングとQUBOの接続によって選択される。

関連論文リスト

Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling [0.0]
本稿では,任意の問題をpolynomial Unconstrained Binary Optimization (PUBO)問題に再構成する汎用手法を提案する。また、擬似非拘束バイナリ最適化(QUBO)問題への総合的な再構成も提供する。この結果から,PUBOの改定がQUBOよりも優れていることが示唆された。
論文参考訳（メタデータ） (2024-11-15T09:23:52Z)
A QUBO Formulation for the Generalized LinkedIn Queens Game [49.1574468325115]
本稿では、LinkedIn Queens ゲームの一連の一般化を解決するために設計された QUBO の定式化について述べる。この定式化は、変数の数と相互作用を最適化しようと試みることで、問題の特定のケースに適応する。また,カラーチェスピース問題 (Coloured Chess Piece Problem) とマックスチェスピース問題 (Max Chess Pieces Problem) という2種類の新しい問題を,対応するQUBOの定式化とともに提示する。
論文参考訳（メタデータ） (2024-10-08T23:54:54Z)
Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
量子デバイスからの全ての出力が有効な経路にマッピングされるため、設計上、ペナルティ項は存在しない。ボソンサンプルを用いて研究を行ったが、この新しい定式化は他の量子デバイスと関係があると信じている。
論文参考訳（メタデータ） (2024-06-20T12:25:00Z)
Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
そこで本稿では,QUBOモデルに基づくMLCTS(Multilevel Constraint Transformation Scheme)を提案する。概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。 MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
論文参考訳（メタデータ） (2024-04-04T17:34:08Z)
Optimizing the Production of Test Vehicles using Hybrid Constrained Quantum Annealing [0.0]
本稿では,D-Wave によるハイブリッド制約2次モデル (CQM) の解法を用いて,満足度という枠組みの問題をモデル化し,その解法を提案する。我々は、CQMソルバの性能は、テスト車両の数を最適化する古典的なソルバに匹敵するものであると結論付けた。
論文参考訳（メタデータ） (2022-03-29T10:36:20Z)
Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文参考訳（メタデータ） (2022-03-11T17:19:26Z)
Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文参考訳（メタデータ） (2022-02-17T18:59:20Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文参考訳（メタデータ） (2021-05-06T17:59:38Z)
QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates [14.905085636501438]
問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。 qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
論文参考訳（メタデータ） (2021-03-19T09:06:12Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。本稿では, 競合ミラー降下法(CMD)を提案する。特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文参考訳（メタデータ） (2020-06-17T22:11:35Z)

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