基于QUBO模型的多维背包问题
山东科技大学, 数学与系统科学学院, 山东青岛 266590
| 摘 要： | 多维背包问题是经典的组合优化问题，目标是找到一组最优的选择方案，以满足所有的约束条件。传统多维背包问题的求解算法普遍存在计算速度慢、计算量随问题维度的增加而呈现指数级增长等缺点。针对以上问题，提出QUBO（二次无约束二进制优化）模型，将多维背包问题表示为一个二次无约束二进制优化问题。使用二进制变量表示多维背包问题的目标函数，通过惩罚项将约束条件以二次项的形式添加到目标函数中，进一步将目标函数转换为QUBO形式，选择量子退火算法找到QUBO问题的最优解。通过开源Python库PyQUBO创建相应模型，在D-Wave平台用量子退火算法求解。结果表明，QUBO模型有较强的数学表达能力使问题更具有结构性，并适用于大规模问题，处理含有大量变量和约束条件的多维背包问题。 |
| 关 键 词： | 多维背包问题; QUBO模型; 二进制; 无约束; 量子退火法 |
| DOI： | 10.57237/j.cst.2023.03.005 |
View:
Downloads:
收稿日期: 2023-08-22
接受日期: 2023-09-14
在线出版日期: 2023-09-19
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 |
参考文献
| [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. |
