Binary BAT algorithm with greedy repair for the discounted 0-1 knapsack problem

Abstract

The discounted 0-1 knapsack problem (D0-1KP) generalizes the classical knapsack problem by partitioning items into groups of three, in which the third item of every group represents a discounted bundle of the first two and at most one item per group may be loaded. This grouping constraint enlarges the search space and makes the problem markedly harder than its classical counterpart. This paper presents BBAT, a binary bat algorithm for the D0-1KP. Bat velocities are mapped to selection probabilities through a sigmoid transfer function, and a greedy repair-and-optimization operator restores feasibility while raising the profit of every candidate solution. The algorithm keeps the small parameter set of the original bat metaheuristic, which limits the tuning effort required before deployment. BBAT was assessed on 14 benchmark instances drawn from the inverse strongly correlated and strongly correlated families, with 30 independent runs per instance. Against two elite genetic algorithms, BBAT improved the best profit found on 12 of the 14 instances and improved the mean profit on 7 of them. The gain in mean profit is concentrated on the inverse strongly correlated family, whereas on strongly correlated instances BBAT attains better peaks at the cost of higher run-to-run variance. These results identify BBAT as a competitive but variance-sensitive solver for the D0-1KP.