Quantum Approaches to the 0/1 Multi-Knapsack Problem: QUBO Formulation, Penalty Parameter Characterization and Analysis
Evren Güney, Joachim C.F. Ehrenthal, Thomas Hanne · 2025
The 0/1 Multi-Knapsack Problem (MKP) is a combinatorial optimization problem with applications in lo gistics, finance, and resource management. Advances in quantum computing have enabled the exploration of problems like the 0/1 MKP through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work develops QUBO formulations for the 0/1 MKP, with a focus on optimizing penalty parameters for encoding constraints. Using simulation experiments across quantum platforms, we evaluate the feasibility of solving small-scale instances of the 0/1 MKP. The results provide insights into the challenges and opportuni ties associated with applying quantum optimization methods for constrained resource allocation problems. © 2025 by SCITEPRESS– Science and Technology Publications, Lda.