A Hybrid Quantum-assisted Column Generation Algorithm for the Fleet
Conversion Problem
- URL: http://arxiv.org/abs/2309.08267v3
- Date: Tue, 12 Mar 2024 09:10:39 GMT
- Title: A Hybrid Quantum-assisted Column Generation Algorithm for the Fleet
Conversion Problem
- Authors: Yagnik Chatterjee, Zaid Allybokus, Marko J. Ran\v{c}i\'c, Eric
Bourreau
- Abstract summary: Fleet Conversion aims to reduce the carbon emissions and cost of operating a fleet of vehicles for a given set of tours.
We show how quantum and classical solvers can be used together to approach an industrial-sized use-case.
- Score: 0.7373617024876725
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of Fleet Conversion aims to reduce the carbon emissions and cost
of operating a fleet of vehicles for a given set of tours. It can be modelled
as a column generation scheme with the Maximum Weighted Independent Set (MWIS)
problem as the slave. Quantum variational algorithms have gained significant
interest in the past several years. Recently, a method to represent Quadratic
Unconstrained Binary Optimization (QUBO) problems using logarithmically fewer
qubits was proposed. Here we use this method to solve the MWIS Slaves and
demonstrate how quantum and classical solvers can be used together to approach
an industrial-sized use-case (up to 64 tours).
Related papers
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Light Cone Cancellation for Variational Quantum Eigensolver Ansatz [3.1347083354427707]
Variational Quantum Algorithms (VQAs) represent a class of algorithms that utilize a hybrid approach.
In this study, we apply a method known as Light Cone Cancellation (LCC) to optimize variational circuits.
We show that LCC yields higher approximation ratios than those cases without LCC.
arXiv Detail & Related papers (2024-04-30T12:31:03Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem.
We benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics.
The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints.
arXiv Detail & Related papers (2023-10-04T12:14:56Z) - Wasserstein Quantum Monte Carlo: A Novel Approach for Solving the
Quantum Many-Body Schr\"odinger Equation [56.9919517199927]
"Wasserstein Quantum Monte Carlo" (WQMC) uses the gradient flow induced by the Wasserstein metric, rather than Fisher-Rao metric, and corresponds to transporting the probability mass, rather than teleporting it.
We demonstrate empirically that the dynamics of WQMC results in faster convergence to the ground state of molecular systems.
arXiv Detail & Related papers (2023-07-06T17:54:08Z) - Formulation of the Electric Vehicle Charging and Routing Problem for a
Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
We show how to exploit multilevel carriers of quantum information -- qudits -- for the construction of constrained quantum optimization algorithms.
We propose a hybrid classical quantum strategy that allows us to sample constrained solutions while greatly reducing the search space of the problem.
arXiv Detail & Related papers (2023-06-07T13:16:15Z) - Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
We present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation.
Existing quantum solvers are limited to solving unconstrained binary programming problems.
Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
arXiv Detail & Related papers (2023-06-01T21:33:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
Coherent control of quantum computations can be used to improve some quantum protocols and algorithms.
We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
arXiv Detail & Related papers (2022-02-10T18:59:52Z) - Quadratic and Higher-Order Unconstrained Binary Optimization of Railway
Rescheduling for Quantum Computing [0.5161531917413706]
This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management.
We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation.
arXiv Detail & Related papers (2021-07-07T14:07:07Z) - 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.