Abstract
Quantum annealing is a promising heuristic method to solve combinatorial optimization problems, and efforts to quantify performance on real-world problems provide insights into how this approach may be best used in practice. We investigate the empirical performance of quantum annealing to solve the Nurse Scheduling Problem (NSP) with hard constraints using the D-Wave 2000Q quantum annealing device. NSP seeks the optimal assignment for a set of nurses to shifts under an accompanying set of constraints on schedule and personnel. After reducing NSP to a novel Ising-type Hamiltonian, we evaluate the solution quality obtained from the D-Wave 2000Q against the constraint requirements as well as the diversity of solutions. For the test problems explored here, our results indicate that quantum annealing recovers satisfying solutions for NSP and suggests the heuristic method is potentially achievable for practical use. Moreover, we observe that solution quality can be greatly improved through the use of reverse annealing, in which it is possible to refine returned results by using the annealing process a second time. We compare the performance of NSP using both forward and reverse annealing methods and describe how this approach might be used in practice.
| Original language | English |
|---|---|
| Article number | 12837 |
| Journal | Scientific Reports |
| Volume | 9 |
| Issue number | 1 |
| DOIs | |
| State | Published - Dec 1 2019 |
Funding
The authors acknowledge Akira Endo for useful discussion at the initial stage of this work. We also thank Joel Gottlieb for carefully reading our manuscript and giving us useful comments. K.I. was partly supported by Scholarship of Overseas Study 2018 (Osaka University) and by Grant-in-Aid for Scientific Research on Innovative Areas, the Ministry of Education, Culture, Sports, Science and Technology, No. 19J11073. T.S.H. acknowledges support from the Department of Energy Office of Science Early Career Research Program. Research funded by the Creative Materials Discovery Program through the National Research Foundation of Korea (NRF) (effective Hamiltonian modeling) funded by the Ministry of Science, ICT and Future Planning (NRF-2016M3D1A1919181). This research used resources of the Oak Ridge Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC05-00OR22725. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan. (http://energy.gov/downloads/doe-public-access-plan).