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

• Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling [0.0]
  We present a generic method to reformulate any problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
  arXiv  Detail & Related papers  (2024-11-15T09:23:52Z)
• A QUBO Formulation for the Generalized LinkedIn Queens Game [49.1574468325115]
  We present a QUBO formulation designed to solve a series of generalisations of the LinkedIn queens game. We adapt this formulation for several particular cases of the problem by trying to optimise the number of variables and interactions. We also present two new types of problems, the Coloured Chess Piece Problem and the Max Chess Pieces Problem, with their corresponding QUBO formulations.
  arXiv  Detail & Related papers  (2024-10-08T23:54:54Z)
• 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)
• 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.