Effect of Valid Cardinality Constraints in Local Branching: The Case of the Knapsack Problem with Setup

Abstract

In this paper, we study the effect of the cardinality constraint when injected into an iterative local branching-based method, especially when tackling the knapsack problem with setup. The designed method is based upon three features: (i) solving a series of mixed linear relaxations, (ii) inducing valid cardinality constraints around some decision variables and,(iii) introducing the local branching strategy for intensifying the search process. First, the mixed linear relaxation can be viewed as driving problem, where it is solved by applying a special black-box solver. Second, the valid cardinality constraints are built according to some favored variables for tightening both lower and upper bounds. Third, the local branching is applied for iteratively intensifying and enhancing the solutions at hand. The performance of the proposed method is evaluated on benchmark instances of the literature, where its achieved results are compared to those reached by the state-of-the-art Cplex solver and the best methods available in the literature. Encouraging results have been obtained.