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 has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Constrained knapsack variants are well-suited for QUBO-based quantum optimization, but adding logical relations can inflate the binary model and complicate penalty selection. This work examines the multi-dimensional knapsack problems augmented with conflict, forcing, and precedence (CFP) constraints using Quadratic Unconstrained Binary Optimization (QUBO) models across classical and quantum platforms. The additional logical constraints are incorporated through quadratic penalty terms that modify existing QUBO coefficients without introducing additional binary variables beyond the slack variables used for the capacity constraints. Computational studies are conducted to assess how each of the three constraint types affects solution behavior, including solution quality, computation time, and sensitivity to penalty parameter magnitudes. The approach is demonstrated on representative small-scale instances using QAOA on IBM Quantum gate-based device and quantum annealing on a D-Wave Advantage processor, with results compared with Gurobi as classical solver. The experiments show that the proposed QUBO formulations achieve optimal or near-optimal solutions for small instances, while showing the sensitivity of current quantum hardware to penalty selection, and scaling. Overall, CFP penalties are variable-neutral relative to the slack-based capacity representation, while the capacity terms dominate logical-qubit count and coupling density. Future work may target more compact or hardware-aware capacity modeling.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.
Combinatorial Optimization (CO) is one of the most important areas in the field of optimization, with practical applications found in every industry, including both the private and public sectors. In recent years, it was discovered that a mathematical formulation known as QUBO (Quadratic Unconstrained Binary Optimization) problem can embrace an exceptional variety of important CO problems found in the industry. In this work, we explore the Quantum Approximate Optimization Algorithm (QAOA) as a quantum computing approach to solve the Knapsack Problem efficiently by formulating the problem as a QUBO model. Here we implemented QAOA on a quantum emulator, leveraging quantum superposition and entanglement to explore multiple solutions simultaneously. The method offers a promising route for solving large, complex scheduling and resource allocation problems that are tough for classical algorithms, with potential applications in logistics, HPC resource scheduling, and energy optimization.
Multidimensional knapsack problem is a classical combinatorial optimization problem, the goal is to find a set of optimal options to satisfy all the constraints. The traditional algorithms for solving multidimensional knapsack problems generally have some disadvantages, such as slow computation speed and exponential increase of computation with the increase of problem dimension. To solve these problems, a QUBO (quadratic unconstrained binary optimization) model is proposed, and the multidimensional knapsack problem is expressed as a quadratic unconstrained binary optimization problem. Binary variables are used to represent the objective function of the multidimensional knapsack problem. The constraints are added to the objective function in the form of quadratic terms by means of penalty terms. The objective function is further transformed into QUBO form. The model is created by PyQUBO, an open source Python library, and solved by quantum annealing algorithm on D-Wave platform. The results show that the QUBO model has a strong ability of mathematical expression, which makes the problem more structured, and is suitable for large-scale problems, dealing with multidimensional knapsack problems with a lot of variables and constraints.