Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- URL: http://arxiv.org/abs/2110.07239v2
- Date: Mon, 18 Oct 2021 02:33:12 GMT
- Title: Solving Large Break Minimization Problems in a Mirrored Double
Round-robin Tournament Using Quantum Annealing
- Authors: Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
- Abstract summary: We show that quantum annealers can be used to solve practical optimization problems.
We compare the performance of quantum annealers with one of the most sophisticated mathematical optimization solvers.
Results: QA was able to determine the exact solution in 0.05 seconds for problems with 20 teams, which is a practical size.
- Score: 0.5156484100374059
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing (QA) has gained considerable attention because it can be
applied to combinatorial optimization problems, which have numerous
applications in logistics, scheduling, and finance. In recent years, research
on solving practical combinatorial optimization problems using them has
accelerated. However, researchers struggle to find practical combinatorial
optimization problems, for which quantum annealers outperform other
mathematical optimization solvers. Moreover, there are only a few studies that
compare the performance of quantum annealers with one of the most sophisticated
mathematical optimization solvers, such as Gurobi and CPLEX. In our study, we
determine that QA demonstrates better performance than the solvers in the break
minimization problem in a mirrored double round-robin tournament (MDRRT). We
also explain the desirable performance of QA for the sparse interaction between
variables and a problem without constraints. In this process, we demonstrate
that the break minimization problem in an MDRRT can be expressed as a 4-regular
graph. Through computational experiments, we solve this problem using our QA
approach and two-integer programming approaches, which were performed using the
latest quantum annealer D-Wave Advantage, and the sophisticated mathematical
optimization solver, Gurobi, respectively. Further, we compare the quality of
the solutions and the computational time. QA was able to determine the exact
solution in 0.05 seconds for problems with 20 teams, which is a practical size.
In the case of 36 teams, it took 84.8 s for the integer programming method to
reach the objective function value, which was obtained by the quantum annealer
in 0.05 s. These results not only present the break minimization problem in an
MDRRT as an example of applying QA to practical optimization problems, but also
contribute to find problems that can be effectively solved by QA.
Related papers
- Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
We introduce a comprehensive quantum solver for binary optimization problems on gate-model quantum computers.
It consistently delivers correct solutions for problems with up to 127 qubits.
We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained binary optimization problems.
arXiv Detail & Related papers (2024-06-03T19:08:01Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry.
In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms.
We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem.
Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
arXiv Detail & Related papers (2023-02-08T17:09:20Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems.
We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
arXiv Detail & Related papers (2022-05-02T21:30:56Z) - 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
We propose a hybrid quantum-classical algorithm for robust fitting.
Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs.
We present results obtained using an actual quantum computer.
arXiv Detail & Related papers (2022-01-25T05:59:24Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
Vehicle routing problem (VRP) is an NP-hard optimization problem.
This work builds a basic VRP solution for 3 and 4 cities using variational quantum eigensolver on a variable ANSATZ.
arXiv Detail & Related papers (2021-12-28T10:20:42Z) - A case study of variational quantum algorithms for a job shop scheduling
problem [0.0]
We apply four variational quantum algorithms running on IBM's superconducting quantum processors to a job shop scheduling problem.
A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster.
F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.
arXiv Detail & Related papers (2021-09-08T16:05:50Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
Linear constraints reduce the size of problems that can be represented in quantum annealers.
We propose a method for solving a sparse QAP by applying a post-processing bit-flip algorithm to solutions obtained by the Ohzeki method.
We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage.
arXiv Detail & Related papers (2020-12-18T09:48:28Z)
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.