This repository hosts experimental code which uses Quantum Annealing (QA) to solve np-hard optimization problems. The author is using the DWave Quantum Hybrid Solver as well as Simulated Annealing (SA) for this purpose.
The main interest is with solving real-world use cases within the airline industry. Code for the original functional prototype for solving Crew Trip problems is included in the code repository.
Also included in the code repository are various side problems that can help understand how to use this new technology. Solvers are implemented using Quadratic Unconstrained Binary Optimization (QUBO) using the DWave BQM and CQM.
The code is provided as an Apache 2 Open Source license.
You can find the Quzzi blog here.
Viable Configurations: Solving 8 Queens problem with BQM and CQM
The author's initial drive behind this work was to prove that Quantum Annealing could be used to solve certain hard problems that airlines of various sizes are confronted with on a daily basis. Despite using powerful classical computing solvers used by the larger airlines, these systems continue to struggle to find optimum results within operational deadlines, especially in a world where strategies are in constant increasing flux.
Having personally written and deployed classical solvers for some of these problems, the author's experience with the constant battle to work around the inpractibility of brute force solvers and "right sizing" heuristic algorithms to obtain viable operational results for np-hard problems made him wish for a "chip" that would handle the combinatorics and solution landscape exploration.
Discovering the existance of the DWave Quantum Annealing technology in 2018, it appeared as a wish come true and he engaged in learning about and experimenting with Quantum computing in general, but more specifically how to use the DWave Quantum Computer to attempt solving the Airline Crew Trip use case.
Quantum Annealing allows finding solutions to large combination problems that are hard to solve with classical computing and offers opportunities for breakthoughs in both speed and solution quality. Furthermore, to code solvers using such a Quantum computer does not require knowledge of physics (although it helps understand why it works).
Problems where there are countless "choices" to be made with consequences on cost/time as these choices interact with each other to form even greater combinations, there is an opportunity to use QA to find the best fit solutions where Classical computing can fail rooted in problem magnitude and time to solution constraints.
Here is a simplistic analogy from the author's point of view:
-
🚶♀️ One tells a classical computer "how" to solve a problem by telling it the steps (code) needed to construct a solution. It is like walking through a labyrinth until the exit is found. You might get exhausted before the end and never find the exit.
-
💥 The Quantum Annealer "knows" how to solve the problem by using a quality rating function one gives it (code) to compare its solutions. The paths to the labyrinth "manifest" themselves and the ones leading to exits rank at the top of the list of possible solutions.
Quzzi aims at making Quantum Annealing solvers more accessible and as simple as possible to anyone by sharing its own experience, through code, examples and training on methodologies.
Quzzi will be listening to anyone interested in this work and more specifically what they wish to learn from it.
Sponsor Quzzi today and get involved to get it to work for you!