Variable neighborhood search for the discounted {0-1} knapsack problem

The discounted {0,1} knapsack problem (D{0-1}KP) is a relatively recent variant of the well-known knapsack problem. In the D{0-1}KP a set of items is partitioned into groups of three items and at most one item can be chosen from each group. In addition, a discount relationship is introduced among items in each group. As for the knapsack problem the aim is to maximize the total profit of the selected items while respecting the knapsack capacity constraint. The D{0-1}KP has been considered in recent years by various authors who proposed different (meta-)heuristics to solve it. In this work we propose a new variable neighborhood search (VNS) to solve the D{0-1}KP. We also consider several greedy heuristics to build an initial feasible solution that can be used by VNS as a starting solution. To evaluate proposed approaches the benchmark instances from the literature are considered. We first assess the quality of initial solutions returned by the greedy algorithms. Then, we analyze the capability of VNS to improve these initial solutions. Finally, we evaluate the performance of VNS compared to the state-of-the-art metaheuristics for solving the D{0-1}KP. The results demonstrate the robustness of VNS which converges to near optimal solutions in a reasonable time. This is especially true when VNS is initialized by solutions returned by greedy algorithms based on linear programming. Moreover, the obtained results show that our VNS based approaches are competitive with the best metaheuristics from the literature for the D{0-1}KP.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

The discounted {0,1} knapsack problem (D{0-1}KP) is a variant of the well-known knapsack problem where items are partitioned into groups and a discount relationship is introduced among items in each group. In this work, a new variable neighborhood search (VNS) algorithm is proposed to solve the D{0-1}KP, and several greedy heuristics are used to build initial feasible solutions. The performance of VNS is evaluated and compared with state-of-the-art metaheuristics, demonstrating its robustness and competitiveness.