{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T00:21:38Z","timestamp":1724545298766},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:00:00Z","timestamp":1724371200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T00:00:00Z","timestamp":1724371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008033","name":"Hochschule Niederrhein","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008033","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quantum annealing has been applied to combinatorial optimization problems in recent years. In this paper we study the possibility to use quantum annealing for solving the combinatorial <jats:sc>FIFO Stack-Up<\/jats:sc> problem, where bins have to be stacked-up from a conveyor belt onto pallets. The problem is NP-hard and can be solved using linear programming approaches. We developed two QUBO (quadratic unconstrained binary optimization) objective functions based on a bin stack-up solution and a pallet stack-up solution for this problem suitable for a quantum annealer. The number of variables was minimized to increase the performance and their dependence on the number of bins and pallets was discussed. The performances of both methods were studied for various small problem sizes on a D-Wave quantum annealer. We found that only tiny instances could be solved and looked at the terms of the QUBO-formulations, which cause the quantum annealer to fail for larger problem sizes. Furthermore we compare the results to the performance of a classic computer using the same QUBO-formulations.<\/jats:p>","DOI":"10.1007\/s42979-024-03082-y","type":"journal-article","created":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:15:25Z","timestamp":1724458525000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["QUBO Models for the FIFO Stack-Up Problem and Experimental Evaluation on a Quantum Annealer"],"prefix":"10.1007","volume":"5","author":[{"given":"Colin","family":"Gebler","sequence":"first","affiliation":[]},{"given":"Jochen","family":"Rethmann","sequence":"additional","affiliation":[]},{"given":"Peer","family":"Ueberholz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,23]]},"reference":[{"key":"3082_CR1","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H. Quantum annealing in the transverse ising model. Phys Rev E. 1998;58:5355\u201363. https:\/\/doi.org\/10.1103\/PhysRevE.58.5355.","journal-title":"Phys Rev E"},{"issue":"1","key":"3082_CR2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00186-015-0518-9","volume":"83","author":"F Gurski","year":"2016","unstructured":"Gurski F, Rethmann J, Wanke E. On the complexity of the FIFO stack-up problem. Math Methods Oper Res. 2016;83(1):33\u201352.","journal-title":"Math Methods Oper Res"},{"key":"3082_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.3389\/fict.2017.00029","volume":"4","author":"F Neukart","year":"2017","unstructured":"Neukart F, Compostella G, Seidel C, Dollen D, Yarkoni S, Parney B. Traffic flow optimization using a quantum annealer. Front ICT. 2017;4:29. https:\/\/doi.org\/10.3389\/fict.2017.00029.","journal-title":"Front ICT"},{"key":"3082_CR4","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1007\/978-3-030-50433-5_42","volume-title":"Comput Sci ICCS 2020","author":"M Borowski","year":"2020","unstructured":"Borowski M, Gora P, Karnas K, B\u0142ajda M, Kr\u00f3l K, Matyjasek A, Burczyk D, Szewczyk M, Kutwin M. New hybrid quantum annealing algorithms for solving vehicle routing problem. In: Krzhizhanovskaya VV, Z\u00e1vodszky G, Lees MH, Dongarra JJ, Sloot PMA, Brissos S, Teixeira J, editors. Comput Sci ICCS 2020. Cham: Springer; 2020. p. 546\u201361."},{"key":"3082_CR5","unstructured":"Harikrishnakumar R, Nannapaneni S, Nguyen NH, Steck JE, Behrman EC. A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem. ArXiv arXiv:abs\/2005.12478 2020"},{"key":"3082_CR6","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1038\/srep00571","volume":"2","author":"A Perdomo-Ortiz","year":"2012","unstructured":"Perdomo-Ortiz A, Dickson N, Drew-Brook M, Rose G, Aspuru-Guzik A. Finding low-energy conformations of lattice protein models by quantum annealing. Sci Rep. 2012;2:571. https:\/\/doi.org\/10.1038\/srep00571.","journal-title":"Sci Rep"},{"key":"3082_CR7","unstructured":"Venturelli D, Marchand DJJ, Rojo G. Quantum annealing implementation of job-shop scheduling 2016"},{"issue":"1","key":"3082_CR8","doi-asserted-by":"publisher","first-page":"3303","DOI":"10.1038\/s41598-021-82740-0","volume":"11","author":"D Inoue","year":"2021","unstructured":"Inoue D, Okada A, Matsumori T, Aihara K, Yoshida H. Traffic signal optimization on a square lattice with quantum annealing. Sci Rep. 2021;11(1):3303. https:\/\/doi.org\/10.1038\/s41598-021-82740-0.","journal-title":"Sci Rep"},{"key":"3082_CR9","unstructured":"Stollenwerk T, Biswas R, Sridhar B. Quantum annealing applied to de-conflicting optimal trajectories for air traffic management. IEEE Trans Intell Transp Syst 2018"},{"key":"3082_CR10","doi-asserted-by":"publisher","unstructured":"Liu J, Spedalieri F, Yao K-T, Potok T, Schuman C, Young S, Patton R, Rose G, Chamka G. Adiabatic quantum computation applied to deep learning networks. Entropy 2018;20(5), https:\/\/doi.org\/10.3390\/e20050380","DOI":"10.3390\/e20050380"},{"key":"3082_CR11","doi-asserted-by":"publisher","first-page":"2","DOI":"10.3389\/fcomp.2019.00002","volume":"1","author":"N Nishimura","year":"2019","unstructured":"Nishimura N, Tanahashi K, Suganuma K, Miyama MJ, Ohzeki M. Item listing optimization for e-commerce websites based on diversity. Front Comput Sci. 2019;1:2. https:\/\/doi.org\/10.3389\/fcomp.2019.00002.","journal-title":"Front Comput Sci"},{"issue":"1","key":"3082_CR12","doi-asserted-by":"publisher","first-page":"7261","DOI":"10.1038\/s41598-021-86274-3","volume":"11","author":"K Utimula","year":"2021","unstructured":"Utimula K, Ichibha T, Prayogo GI, Hongo K, Nakano K, Maezono R. A quantum annealing approach to ionic diffusion in solids. Sci Rep. 2021;11(1):7261. https:\/\/doi.org\/10.1038\/s41598-021-86274-3.","journal-title":"Sci Rep"},{"key":"3082_CR13","doi-asserted-by":"crossref","unstructured":"Yarkoni S, Raponi E, B\u00e4ck T, Schmitt S. Quantum annealing for industry applications: Introduction and review. Rep Prog Phys 2021;85","DOI":"10.1088\/1361-6633\/ac8c54"},{"key":"3082_CR14","doi-asserted-by":"crossref","unstructured":"Pochart T, Jacquot P, Mikael J. On the challenges of using d-wave computers to sample boltzmann random variables. In: 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C), 2021;137\u2013140","DOI":"10.1109\/ICSA-C54293.2022.00034"},{"key":"3082_CR15","unstructured":"J\u00fcnger M, Lobe E, Mutzel P, Reinelt G, Rendl F, Rinaldi G, Stollenwerk T. Performance of a quantum annealer for ising ground state computations on chimera graphs. CoRR arXiv:abs\/1904.11965 2019"},{"key":"3082_CR16","doi-asserted-by":"publisher","unstructured":"Karp RM. Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York 1972. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"3082_CR17","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/978-3-030-50743-5_10","volume-title":"High Performance Computing","author":"S Zbinden","year":"2020","unstructured":"Zbinden S, B\u00e4rtschi A, Djidjev H, Eidenbenz S. Embedding algorithms for quantum annealers with chimera and pegasus connection topologies. In: Sadayappan P, Chamberlain BL, Juckeland G, Ltaief H, editors. High Performance Computing. Cham: Springer; 2020. p. 187\u2013206."},{"key":"3082_CR18","unstructured":"Boothby K, Bunyk P, Raymond J, Roy A. Next-generation topology of D-wave quantum processors 2020"},{"key":"3082_CR19","doi-asserted-by":"publisher","unstructured":"Cai J, Macready WG, Roy A. A practical heuristic for finding graph minors 2014. https:\/\/doi.org\/10.48550\/ARXIV.1406.2741","DOI":"10.48550\/ARXIV.1406.2741"},{"key":"3082_CR20","doi-asserted-by":"crossref","unstructured":"Gurski F, Rethmann J, Wanke E. Integer programming models and parameterized algorithms for controlling palletizers. CoRR 2015 arXiv:1509.07278 [cs.DS]","DOI":"10.1007\/978-3-319-28697-6_28"},{"issue":"2","key":"3082_CR21","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1007\/s00291-019-00549-w","volume":"41","author":"F Gurski","year":"2019","unstructured":"Gurski F, Rehs C, Rethmann J, Wanke E. Controlling distribution conveyors and multi-line palletizers: theoretical foundations and online algorithms. OR Spectr. 2019;41(2):581\u2013611.","journal-title":"OR Spectr"},{"key":"3082_CR22","doi-asserted-by":"publisher","unstructured":"Nemhauser GL, Wolsey LA. The Scope of Integer and Combinatorial Optimization. Wiley interscience series in discrete mathematics and optimization. Wiley, New Jersey 1988. https:\/\/doi.org\/10.1002\/9781118627372.ch1","DOI":"10.1002\/9781118627372.ch1"},{"key":"3082_CR23","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas A. Ising formulations of many np problems. Front Phys. 2014;2:5. https:\/\/doi.org\/10.3389\/fphy.2014.00005.","journal-title":"Front Phys"},{"key":"3082_CR24","doi-asserted-by":"publisher","unstructured":"Gurski F, Rethmann J, Wanke E. A Practical Approach for the FIFO Stack-Up Problem. In: Thi, H.A.L., Dinh, T.P., Nguyen, N.T. (eds.) Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO). Advances in Intelligent Systems and Computing, vol. 360, pp. 141\u2013152. Springer, Metz, France 2015. https:\/\/doi.org\/10.1007\/978-3-319-18167-7_13","DOI":"10.1007\/978-3-319-18167-7_13"},{"key":"3082_CR25","doi-asserted-by":"publisher","unstructured":"Gurski F, Rethmann J, Wanke E. An Experimental Study of Algorithms for Controlling Palletizers. In: Doerner, K.F., Ljubic, I., Pflug, G., Tragler, G. (eds.) Operations Research Proceedings (OR 2015), pp. 27\u201334. Springer, Vienna, Austria 2017. https:\/\/doi.org\/10.1007\/978-3-319-42902-1_4","DOI":"10.1007\/978-3-319-42902-1_4"},{"key":"3082_CR26","doi-asserted-by":"publisher","unstructured":"Pusey-Nazzaro L, Date P. Adiabatic quantum optimization fails to solve the knapsack problem. arXiv 2020. https:\/\/doi.org\/10.48550\/ARXIV.2008.07456","DOI":"10.48550\/ARXIV.2008.07456"},{"key":"3082_CR27","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/s42979-020-00431-5","volume":"2","author":"N Huang","year":"2021","unstructured":"Huang N, Roje D. A new qubo objective function for solving the maximum common subgraph isomorphism problem via quantum annealing. SN Comput Sci. 2021;2:186. https:\/\/doi.org\/10.1007\/s42979-020-00431-5.","journal-title":"SN Comput Sci."},{"key":"3082_CR28","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/s42979-021-00483-1","volume":"2","author":"D Vert","year":"2021","unstructured":"Vert D, Sirdey R, Louise S. Benchmarking quantum annealing against \"hard\" instances of the bipartite matching problem. SN Comput Sci. 2021;2:106. https:\/\/doi.org\/10.1007\/s42979-021-00483-1.","journal-title":"SN Comput Sci."},{"key":"3082_CR29","doi-asserted-by":"publisher","unstructured":"Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I, Mauerer W, Linnhoff-Popien C. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Front ICT 2019;6. https:\/\/doi.org\/10.3389\/fict.2019.00013","DOI":"10.3389\/fict.2019.00013"},{"issue":"12142","key":"3082_CR30","first-page":"488","volume":"2020","author":"C Roch","year":"2020","unstructured":"Roch C, Phan T, Feld S, M\u00fcller R, Gabor T, Linnhoff-Popien C. A quantum annealing algorithm for finding pure nash equilibria in graphical games. Comput Sci ICCS. 2020;2020(12142):488\u2013501.","journal-title":"Comput Sci ICCS"},{"key":"3082_CR31","doi-asserted-by":"crossref","unstructured":"Su J, Tu T, He L. A quantum annealing approach for boolean satisfiability problem. In: 2016 53nd ACM\/EDAC\/IEEE Design Automation Conference (DAC), 2016;1\u20136","DOI":"10.1145\/2897937.2897973"},{"issue":"10","key":"3082_CR32","doi-asserted-by":"crossref","first-page":"1822","DOI":"10.1016\/j.dam.2007.08.045","volume":"156","author":"B Yang","year":"2008","unstructured":"Yang B, Cao Y. Digraph searching, directed vertex separation and directed pathwidth. Discrete Appl Math. 2008;156(10):1822\u201337.","journal-title":"Discrete Appl Math."},{"key":"3082_CR33","doi-asserted-by":"publisher","first-page":"0823","DOI":"10.1126\/sciadv.aau0823","volume":"5","author":"R Hamerly","year":"2019","unstructured":"Hamerly R, Inagaki T, McMahon P, Venturelli D, Marandi A, Onodera T, Ng E, Langrock C, Inaba K, Honjo T, Enbutsu K, Umeki T, Kasahara R, Utsunomiya S, Kako S, Kawarabayashi K-I, Byer R, Fejer M, Mabuchi H, Yamamoto Y. Experimental investigation of performance differences between coherent ising machines and a quantum annealer. Sci Adv. 2019;5:0823. https:\/\/doi.org\/10.1126\/sciadv.aau0823.","journal-title":"Sci Adv."},{"key":"3082_CR34","doi-asserted-by":"publisher","unstructured":"Okada S, Ohzeki M, Terabe M, Taguchi S. Improving solutions by embedding larger subproblems in a d-wave quantum annealer. Sci Rep. 2019;9(2098) https:\/\/doi.org\/10.1038\/s41598-018-38388-4","DOI":"10.1038\/s41598-018-38388-4"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-03082-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-024-03082-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-03082-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:27:28Z","timestamp":1724459248000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-024-03082-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,23]]},"references-count":34,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,10]]}},"alternative-id":["3082"],"URL":"https:\/\/doi.org\/10.1007\/s42979-024-03082-y","relation":{},"ISSN":["2661-8907"],"issn-type":[{"type":"electronic","value":"2661-8907"}],"subject":[],"published":{"date-parts":[[2024,8,23]]},"assertion":[{"value":"15 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"818"}}