Optimising Rolling Stock Planning including Maintenance with Constraint Programming and Quantum Annealing

• URL: http://arxiv.org/abs/2109.07212v3
• Date: Mon, 25 Sep 2023 07:01:01 GMT
• Title: Optimising Rolling Stock Planning including Maintenance with Constraint Programming and Quantum Annealing
• Authors: Patricia Bickert, Cristian Grozea, Ronny Hans, Matthias Koch, Christina Riehn, Armin Wolf
• Abstract summary: We propose and compare Constraint Programming (CP) and Quantum Annealing (QA) approaches for rolling stock assignment optimisation. In the CP approach, we model the problem with an Alldifferent constraint, extensions of the Element constraint, and logical implications. For the QA approach, we develop a quadratic unconstrained binary optimisation (QUBO) model.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose and compare Constraint Programming (CP) and Quantum Annealing (QA) approaches for rolling stock assignment optimisation considering necessary maintenance tasks. In the CP approach, we model the problem with an Alldifferent constraint, extensions of the Element constraint, and logical implications, among others. For the QA approach, we develop a quadratic unconstrained binary optimisation (QUBO) model. For evaluation, we use data sets based on real data from Deutsche Bahn and run the QA approach on real quantum computers from D-Wave. Classical computers are used to evaluate the CP approach as well as tabu search for the QUBO model. At the current development stage of the physical quantum annealers, we find that both approaches tend to produce comparable results.

Related papers

• Approximating under the Influence of Quantum Noise and Compute Power [3.0302054726041017]
  The quantum approximate optimisation algorithm (QAOA) is at the core of many scenarios that aim to combine the power of quantum computers and classical high-performance computing appliances for optimisation. We study factors that affect solution quality and temporal behaviour of four QAOA variants using comprehensive density-matrix-based simulations. Our results, accompanied by a comprehensive reproduction package, show strong differences between QAOA variants that can be pinpointed to narrow and specific effects.
  arXiv  Detail & Related papers  (2024-08-05T07:48:49Z)
• Polynomial Reduction Methods and their Impact on QAOA Circuits [2.4588375162098877]
  We show how higher-order problem formulations can be used to leverage different desired non-functional properties for quantum optimisation. Our study shows that the approach allows us to satisfy different trade-offs, and suggests various possibilities for the future construction of general-purpose abstractions.
  arXiv  Detail & Related papers  (2024-06-13T07:43:18Z)
• Compiler for Distributed Quantum Computing: a Reinforcement Learning Approach [6.347685922582191]
  We introduce a novel compiler that prioritizes reducing the expected execution time by jointly managing the generation and routing of EPR pairs. We present a real-time, adaptive approach to compiler design, accounting for the nature of entanglement generation and the operational demands of quantum circuits. Our contributions are twofold: (i) we model the optimal compiler for DQC using a Markov Decision Process (MDP) formulation, establishing the existence of an optimal algorithm, and (ii) we introduce a constrained Reinforcement Learning (RL) method to approximate this optimal compiler.
  arXiv  Detail & Related papers  (2024-04-25T23:03:20Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Measurement-Based Quantum Approximate Optimization [0.24861619769660645]
  We focus on measurement-based quantum computing protocols for approximate optimization. We derive measurement patterns for applying QAOA to the broad and important class of QUBO problems. We discuss the resource requirements and tradeoffs of our approach to that of more traditional quantum circuits.
  arXiv  Detail & Related papers  (2024-03-18T06:59:23Z)
• QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing [4.589533935256401]
  The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence. Recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup. We introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing.
  arXiv  Detail & Related papers  (2023-09-22T07:37:20Z)
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models [62.997667081978825]
  We build over a proposed framework for evaluating the generalization performance of generative models. We establish the first comparative race towards practical quantum advantage (PQA) between classical and quantum generative models. Our results suggest that QCBMs are more efficient in the data-limited regime than the other state-of-the-art classical generative models.
  arXiv  Detail & Related papers  (2023-03-27T22:48:28Z)
• Evaluating the Convergence of Tabu Enhanced Hybrid Quantum Optimization [58.720142291102135]
  We introduce the Tabu Enhanced Hybrid Quantum Optimization metaheuristic approach useful for optimization problem solving on a quantum hardware. We address the theoretical convergence of the proposed scheme from the viewpoint of the collisions in the object which stores the tabu states, based on the Ising model.
  arXiv  Detail & Related papers  (2022-09-05T07:23:03Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• 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)

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.