Local branching-based algorithms for the disjunctively constrained knapsack problem

The disjunctively constrained knapsack problem (DCKP) is a variant of the well-known single constrained knapsack problem with special disjunctive constraints. This paper investigates the use of the local branching techniques for solving large-scale DCKP. Three versions of the algorithm are considered. The first version is based on the standard local branching which uses a starting solution provided by a specialized rounding solution procedure. The second version applies a two-phase solution procedure embedded in the local branching. For each subtree, the procedure series to construct the set of objects containing the assigned variables and a second set including the free variables. The first set provides a partial local solution to the DCKP, whereas, for the second set, a truncated exact tree-search is applied for completing the partial local feasible solution. Finally, a diversification strategy is considered constituting the third version of the algorithm. All versions of the proposed algorithm are computationally analyzed on a set of benchmark instances of the literature and the obtained solutions are compared to those provided by existing algorithms. Encouraging results have been obtained. (C) 2011 Elsevier Ltd. All rights reserved.