The set-union knapsack problem (SUKP) is a generalization of the standard 0–۱ knapsack problem. It is NP-hard, and has several industrial applications. Several approximation and heuristic approaches have been previously presented for solving the SUKP. However, the solution quality still needs to be enhanced. This work develops a hybrid binary particle swarm optimization with tabu search (HBPSO/TS) to solve the SUKP. First, an adaptive penalty function is utilized to evaluate the quality of solutions during the search. This method endeavours to explore the boundary of the feasible solution space. Next, based on the characteristics of the SUKP, a novel position updating procedure is designed. The newly generated solutions obtain the good structures of previously found solutions. Then, a tabu based mutation procedure is introduced to lead the search to enter into new hopeful regions. Finally, we design a tabu search procedure to improve the exploitation ability. Furthermore, a gain updating strategy is employed to reduce the solution time. The HBPSO/TS is tested on three sets of 30 benchmark instances, and comparisons with current state-of-the-art algorithms are performed. Experimental results show that HBPSO/TS performs much better than the other algorithms in terms of solution quality. Moreover, HBPSO/TS improves new best results at 28 out of the 30 instances. The impact of the main parts of the HBPSO/TS is also experimentally investigated.

Introduction

The SUKP has been shown to be NP-hard (Goldschmidt et al., 1994), and has been used in various domains including database partitioning (Navathe, Ceri, Wiederhold, & Dou, 1984), financial decision making (Kellerer, Pferschy, & Pisinger, 2004), flexible manufacturing (Tang & Denardo, 1988), and smart cities (Tu & Xiao, 2016), etc. It has been also used in practical applications such as the key-pose caching problem (Lister, Laycock, & Day, 2010). In the key-pose caching problem, for each frame, there are n characters which will be rendered whereby each character interpolates a set of m key poses. For a character, its key-poses remain valid for a period of time, and can be shared with other characters. The keypose caching problem maximizes the number of rendered characters by populating a cache of locations with skinned key-poses. Let the set of elements U be equal to the set of all key-poses needed by the crowd in a given frame, and the weight of each key-pose is set as 1. Each item refers to a crowd member, and its profit is equal to the number of occurrences of the key-pose pair. Then, the key-pose caching problem can be formulated as the SUKP.