Solving assignment problems via Quantum Computing: a case-study in train seating arrangement
Ilaria Gioda, Davide Caputo, Edoardo Fadda, Daniele Manerba, Blanca Silva Fernández, Roberto Tadei
DOI: http://dx.doi.org/10.15439/2021F74
Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 217–220 (2021)
Abstract. In recent years, researchers have oriented their studies towards Quantum Computing because it should allow the resolution of complex problems currently considered to be intractable. This work focuses on solving an assignment problems, by exploiting this novel computational approach. A case-study, denoted as the Seating Arrangement Optimization problem, is considered. It is modeled through the Quadratic Unconstrained Binary Optimization paradigm and solved through two tools made available by the D-Wave Systems company, QBSolv and a quantum-classical hybrid system. The obtained experimental results are compared in terms of solution quality and computational efficiency.
References
- Marchenkova A., "What’s the difference between quantum annealing and universal gate quantum computers?", https://medium.com/quantum-bits/what-s-the-difference-between-quantum-annealing-and-universal-gate-quantum-computers-c5e5099175a1
- Booth, M. & Reinhardt, S.P. "Partitioning Optimization Problems for Hybrid Classical / Quantum Execution", Technical Report (2017)
- Glover, F., Kochenberger, G. & Du, Y. "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models." 4OR-Q J Oper Res 17, 335–371 (2019). https://doi.org/10.1007/s10288-019-00424-y
- S. B. Hengeveld, N. Rubiano da Silva, D. S. Gonçalves, P. H. Souto Ribeiro, A. Mucherino, Solving the One-dimensional Distance Geometry Problem by Optical Computing, arXiv e-print, https://arxiv.org/abs/2105.12118, version 1, May 2021.