Multidimensional Knapsack Problem Based on QUBO Model

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.