Iterated two-phase local search for the Set-Union Knapsack Problem

摘要

Many practical decision-making problems involve selecting a subset of objects from a set of candidate objects such that the selected objects optimize a given objective while satisfying some constraints. Knapsack problems such as the Set-union Knapsack Problem (SUKP) are general models that allow such decision-making problems to be conveniently formulated. Given a set of weighted elements and a set of items with profits where each item is composed of a subset of elements, the SUKP aims to pack a subset of items in a capacity-constrained knapsack in a way that the total profit of the selected items is maximized while their weights do not exceed the knapsack capacity. In this work, we present an effective iterated two-phase local search algorithm for this NP-hard problem. The proposed algorithm iterates through two complementary search phases: a local optima exploration phase to discover local optimal solutions, and a local optima escaping phase to drive the search to unexplored regions. We show the competitiveness of the algorithm compared to the state-of-the-art methods in the literature. Specifically, the algorithm discovers 18 improved best results (new lower bounds) for the 30 benchmark instances and matches the best-known results for the 12 remaining instances. We also report the first computational results with the general CPLEX solver, including 6 proven optimal solutions. Finally, we investigate the impacts of the key ingredients of the algorithm on its performance. (C) 2019 Elsevier B.V. All rights reserved.