GPS: A new TSP formulation for its generalizations type QUBO
- URL: http://arxiv.org/abs/2110.12158v3
- Date: Tue, 18 Jan 2022 19:18:08 GMT
- Title: GPS: A new TSP formulation for its generalizations type QUBO
- Authors: Sa\'ul Gonz\'alez-Bermejo, Guillermo Alonso-Linaje, Parfait
Atchade-Adelomou
- Abstract summary: We propose a new Quadratic Unconstrained Binary Optimization (QUBO) formulation of the Travelling Salesman Problem (TSP)
We overcome the best formulation of the Vehicle Routing Problem (VRP) in terms of the minimum number of necessary variables.
Finally, we tested whether the correctness of the formulation by entering it into a QUBO problem solver.
- Score: 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.
Related papers
- Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes.
Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices.
arXiv Detail & Related papers (2024-06-20T12:25:00Z) - Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
We propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables.
For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver.
The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.
arXiv Detail & Related papers (2024-04-04T17:34:08Z) - Quantum Annealing Solutions for the Closest String Problem with D-Wave
Systems [0.0]
Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory.
Two QUBO formulations have been proposed, with one being a slight modification over the other.
DWave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns.
arXiv Detail & Related papers (2023-10-19T16:03:25Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - Optimizing the Production of Test Vehicles using Hybrid Constrained
Quantum Annealing [0.0]
We model the problem in the framework of satisfiability and solve it by utilizing the hybrid constrained quadratic model (CQM) solver provided by D-Wave.
We conclude that the performance of the CQM solver is comparable to classical solvers in optimizing the number of test vehicles.
arXiv Detail & Related papers (2022-03-29T10:36:20Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z) - QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver
Surrogates [14.905085636501438]
We build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem.
In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce good choices of penalty parameters.
QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.
arXiv Detail & Related papers (2021-03-19T09:06:12Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z) - Competitive Mirror Descent [67.31015611281225]
Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints.
We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information.
As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
arXiv Detail & Related papers (2020-06-17T22:11:35Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.