QUBO formulations and characterization of penalty parameters for the multi-knapsack problem
Loading...
Author (Corporation)
Publication date
2025
Typ of student thesis
Course of study
Collections
Type
01A - Journal article
Editors
Editor (Corporation)
Supervisor
Parent work
IEEE Access
Special issue
DOI of the original publication
Link
Series
Series number
Volume
13
Issue / Number
Pages / Duration
47086-47098
Patent number
Publisher / Publishing institution
IEEE
Place of publication / Event location
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using Quadratic Unconstrained Binary Optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants—the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)—and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate Optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters significantly affects quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Finally, we outline directions for future research in solvingMKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
ISSN
2169-3536
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
Gold
License
Citation
Güney, E., Ehrenthal, J., & Hanne, T. (2025). QUBO formulations and characterization of penalty parameters for the multi-knapsack problem. IEEE Access, 13, 47086–47098. https://doi.org/10.1109/ACCESS.2025.3550788