Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
QUBO Models for the FIFO Stack-Up Problem and Experimental Evaluation
on a Quantum Annealer
Springer Nature Computer Science (Volume 5, Number 7, 818)
Abstract
| 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 FIFO Stack-Up 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. |