The Local Branching as a Learning Strategy in the Evolutionary Algorithm: The Case of the Set-Union Knapsack Problem

In this paper, we introduce the local branching as a learning strategy for approximately solving the set-union knapsack problem; that is an NP-hard combination optimization problem. The designed method is based upon three features: (i) applying a swarm optimization for generating a set of current particles, (ii) using an iterative search for providing a series of diversified solutions linking some particles of the population and, (iii) injecting a local branching as a learning strategy for enhancing the global best solution: it can be viewed as a driving strategy employed for guiding particles towards the best position. The performance of the method is evaluated on benchmark instances of the literature, where its provided bounds are compared to those reached by the best methods available in the literature. New bounds have been discovered.