Research on Greedy Core Algorithms via Piecewise Sorting for Discounted {0-1} Knapsack Problem

doi:10.3778/j.issn.1673-9418.2106033

Abstract

Abstract: The greedy core method of D{0-1}KP problem is an approximate solution algorithm, which usually adopts the design pattern of divide and conquer algorithm, and divides subproblems by estimated core interval. Its performance is closely related to the accuracy of core interval size. The main way to improve the algorithm is to optimize core interval estimation. On the basis of studying the concept of {0-1}KP core, a repaired definition of D{0-1}KP core interval is proposed, and a piecewise sorting strategy is constructed to reduce the size of its core interval. Thus, the greedy core method of D{0-1}KP is improved. The repaired greedy core acceleration dynamic programming algorithm (RGCADP) and the repaired greedy core acceleration dynamic programming algorithm via piecewise sorting (RGCADP_PS) are designed. Experimental results on D{0-1}KP standard datasets show that the average solving time of RGCADP and RGCADP_PS is improved by 71.3% and 77.2% compared with the basic dynamic programming algorithm (BDP). The average solution error rate of proposed algorithms can be reduced by 0.5 percentage points and 4.7 percentage points compared?with that of the particle swarm optimization based greedy repair algorithm for D{0-1}KP (PSO-GRDKP) and the greedy core acceleration dynamic programming algorithm (GCADP). The average solving time improvement rate of RGCADP_PS is 5.9% higher than that of RGCADP.

Key words: discounted {0-1} knapsack problem, repaired core interval definition, greedy core algorithm, piece-wise sorting, greedy core dynamic programming acceleration algorithm

摘要： 折扣{0-1}背包问题（D{0-1}KP）的贪心核算法是一种近似解算法，常通过估算核区间划分子问题，采用分治算法设计求解算法，算法性能与核区间估计准确性密切相关，核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上，提出D{0-1}KP核区间的修正定义，构建分段排序策略以缩减核区间规模，改进了D{0-1}KP贪心核算法，设计了修复贪心核动态规划加速算法（RGCADP）、分段排序贪心核动态规划加速算法（RGCADP_PS）。两个算法在D{0-1}KP标准数据集上的实验结果表明：与基本动态规划算法（BDP）相比，RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%；RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法（PSO-GRDKP）0.5个百分点，低于贪心核加速动态规划（GCADP）算法4.7个百分点；RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

关键词: 折扣{0-1}背包问题, 核区间定义修正, 贪心核算法, 分段排序, 贪心核动态规划加速算法

DAI Zuhua, LIU Yuanyuan, DI Shilong, FAN Qi. Research on Greedy Core Algorithms via Piecewise Sorting for Discounted {0-1} Knapsack Problem[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(3): 595-607.

代祖华, 刘园园, 狄世龙, 樊琦. 折扣{0-1}背包问题之分段排序贪心核算法研究[J]. 计算机科学与探索, 2023, 17(3): 595-607.

References

[1] BALAS E, ZEMEL E. An algorithm for large zero-one knapsack problems[J]. Operations Research, 1980, 28(5): 1130-1154.
[2] PISINGER D. Core problems in knapsack algorithms[J]. Operations Research, 1999, 47(4): 570-575.
[3] GUDER J. Discounted knapsack problems for pairs of items[D]. Nuremberg: University of Erlangen-Nurnberg, 2005.
[4] GULDAN B. Heuristic and exact algorithms for discounted knapsack problems[D]. Nuremberg: University of Erlangen-Nuremberg, 2007．
[5] RONG A, FIGUEIRA J R, KLAMROTH K. Dynamic pro-gramming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics & Computation, 2012, 218(12): 6921-6933.
[6] HE Y C, WANG X Z, HE Y L, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem[J]. Information Sciences, 2016, 369: 634-647.
[7] 贺毅朝, 王熙照, 李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报, 2016, 39(12): 2614-2630.
HE Y C, WANG X Z, LI W B, et al. Research on genetic algorithms for discounted {0-1} knapsack problem[J]. Chinese Journal of Computers, 2016, 39(12): 2614-2630.
[8] 杨洋, 潘大志, 贺毅朝. 核加速遗传算法求解折扣{0-1}背包问题[J]. 西华师范大学学报(自然科学版), 2018, 39(2):165-172.
YANG Y, PAN D Z, HE Y C. Core accelerated genetic algorithm to solve the discount {0-1} knapsack problem[J]. Journal of China West Normal University (Natural Sciences Edition), 2018, 39(2): 165-172.
[9] 徐小平, 徐丽, 王峰, 等. 基于Lagrange插值的学习猴群算法求解折扣{0-1}背包问题[J]. 计算机应用, 2020, 40(11): 19-24.
XU X P, XU L, WANG F, et al. Learning monkey algorithm based on Lagrange interpolation to solve discounted {0-1}knapsack problem[J]. Journal of Computer Applications, 2020, 40(11): 19-24.
[10] WU C C, ZHAO J L, FENG Y H, et al. Solving discounted {0-1} knapsack problems by a discrete hybrid teaching-learning-based optimization algorithm[J]. Applied Intelligence, 2020, 50(12): 1872-1888.
[11] 史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
SHI W X, YANG Y, BAO S L. Greedy core acceleration dynamic programming algorithm for solving discounted{0-1}knapsack problem[J]. Journal of Computer Applications, 2019, 39(7): 1912-1917.
[12] HE Y C, WANG X Z, GAO S G. Ring theory-based evolutionary algorithm and its application to D{0-1}KP[J]. Applied Soft Computing, 2019, 77: 714-722.
[13] PISINGER D. An expanding core algorithm for the exact 0-1 knapsack problem[J]. European Journal of Operational Research, 1995, 87(1): 175-187.
[14] BEIER R, V?CKING B. Probabilistic analysis of knapsack core algorithms[C]//Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Jan 11-14, 2004. Philadelphia: SIAM, 2004: 468-477.
[15] GOMESDASILVA C, CLIMACO J, RUIFIGUEIRA J. Core problems in bi-criteria {0-1}-knapsack problems[J]. Computers & Operations Research, 2008, 35: 2292-2306.
[16] FUJIMOTO N. A pseudo-polynomial time algorithm for solving the knapsack problem in polynomial space[C]//LNCS 10043: Proceedings of the 10th International Conference, Hong Kong, China, Dec 16-18, 2016. Cham: Springer, 2016:624-638.