Multidimensional Knapsack Problem Based on QUBO Model
College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, China
| Abstract: | 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. |
| Keywords: | Multidimensional Backpack Problem; QUBO Model; Binary; No Constraints; Quantum Annealing Algorithm |
| DOI: | 10.57237/j.cst.2023.03.005 |
View:
Downloads:
Received: 22 August 2023
Accepted: 14 September 2023
Published Online: 19 September 2023
References
| [1] | Genserik L L Reniers, Kenneth Sörensen. An Approach for Optimal Allocation of Safety Resources: Using the Knapsack Problem to Take Aggregated Cost-Efficient Preventive Measures [J]. Risk Analysis, 2013, 33(11): 2056-2067. |
| [2] | 陈建荣. 求解0-1背包问题的改进二进制捕鱼算法 [J]. 计算机技术与发展, 2023, 33(5): 187-193. |
| [3] | Li Junbao, Chu Shuchuan, Yang J S P. Discriminant Pattern Classification [J]. Journal of Digital Information Management, 2008, 6(2): 203-207. |
| [4] | LI V C, LIANG Y C, CHANG H F. Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method [J]. Computers & Operations Research, 2012, 39(9): 2111-2121. |
| [5] | 孙佳宁, 马海龙, 张立臣, 李鹏. 求解0-1背包问题的融合贪心策略的回溯算法 [J]. 计算机技术与发展, 2022, 32(02): 190-195. |
| [6] | 乔丽娟, 徐岩. 基于0-1背包问题的综合性实验研究 [J]. 电子技术, 2018, 47(11): 15-17. |
| [7] | 熊伟清, 魏平, 王小权. 蚁群算法求解多维 0/1 背包问题 [J]. 计算机工程与科学, 2006, 28(10): 78-79. |
| [8] | Abdellah Rezoug, Mohamed Bader-El-Den&Dalila Boughaci. Guided genetic algorithm for the multidimensional knapsack problem [J]. Memetic Computing, 2018, 10(1): 29-42. |
| [9] | 李枝勇, 马良, 张惠珍. 求解0/1背包问题的自适应元胞粒子群算法 [J]. 计算机工程, 2014, 40(10): 198-203. |
| [10] | 许小勇. 基于改进的模拟退火算法求解 0/1 背包问题 [J]. 海南大学学报: 自然科学版, 2008, 26(4): 356-358. |
| [11] | Luis Fernando Mingo López, Nuria Gómez Blas, Alberto Arteta Albert. Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations [J]. Soft Computing, 2018, 22: 2567-2582. |
| [12] | 钱淑渠, 武慧虹, 林妤. 求解高维动态背包问题的克隆修复免 [J]. 计算机工程, 2017, 43(9): 220-227. |
| [13] | FENG Y H, WANG G G. A binary moth search algorithm based on self-learning for multidimensional knapsack problem [J]. Future Generation Computer Systems, 2022, 126: 48-64. |
| [14] | 马立肖, 赵占芳. 一种求解背包问题的混合差异演化算法 [J]. 计算机工程, 2012, 38(7): 164-167. |
| [15] | José García, Carlos Maureira. A KNN quantum cuckoo search algorithm applied to the multidimensional knapsack problem [J]. Applied Soft Computing, 2021, 102. |
| [16] | Hamza Onoruoiza, Abubakar Bala. An improved chemical reaction optimisation algorithm for the 0-1 knapsack problem [J]. International Journal of Bio-Inspired Computation, 2022, 19(4): 253-266. |
| [17] | 罗亚波, 滕红玺. 求解0-1背包问题的牵制平衡算法 [J]. 工业工程, 2023, 26(3): 116-123. |
| [18] | Siddharth Jain. Solving the Traveling Salesman Problem on the D-Wave Quantum Computer [J]. Frontiers in Physics, 2021, 9. |
| [19] | Fred Glover, Gary Kochenberger, Rick Hennig, Yu Du. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models [J]. Annals of Operations Research, 2022, 314(1): 141-183. |
| [20] | Christos Papalitsas, Theodore Andronikos, Konstantinos Giannakis, Georgia Theocharopoulou, Sofia Fanarioti. A QUBO Model for the Traveling Salesman Problem with Time Windows [J]. Algorithms 2019, 2022, 12(11): 224. |
| [21] | 潘大志, 蒋妍, 刘雅文. 求解多维背包问题的双决策交互差异算法 [J]. 计算机工程, 2023, 49(7): 21-33. |
| [22] | Mashiyat Zaman, Kotaro Tanahashi, Shu Tanaka. PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form [J]. IEEE Transactions on Computers, 2021, 71(4): 838-850. |
| [23] | Peter J. Bussey. Modern quantum mechanic [J]. Contemporary Physics, 2021, 62(1): 53-54. |
| [24] | Andrew Lucas. Ising formulations of many NP problems [J]. Frontiers in Physics, 2014, 2. |
| [25] | V. Mehta, F. Jin, K. Michielsen, H. De Raedt. On the hardness of quadratic unconstrained binary optimization problems [J]. Frontiers in Physics, 2022, 10. |
Join the Editorial Board
We invite active, qualified and high profile scientists and researchers to join as Editorial Board Members.
Join UsBecome a Reviewer
Scholars with a strong interest in reviewing are invited to join the reviewer panel to ensure the quality of the research to be published.
Join Us