QUBO formulations and characterization of penalty parameters for the multi-knapsack problem
Lade...
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2025
Typ der Arbeit
Studiengang
Typ
01A - Beitrag in wissenschaftlicher Zeitschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
IEEE Access
Themenheft
DOI der Originalpublikation
Link
Reihe / Serie
Reihennummer
Jahrgang / Band
13
Ausgabe / Nummer
Seiten / Dauer
47086-47098
Patentnummer
Verlag / Herausgebende Institution
IEEE
Verlagsort / Veranstaltungsort
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
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.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
ISSN
2169-3536
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
Peer-Review der ganzen Publikation
Open Access-Status
Gold
Lizenz
Zitation
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