کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1134958 | 1489100 | 2011 | 10 صفحه PDF | دانلود رایگان |
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 serves 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.
Journal: Computers & Industrial Engineering - Volume 60, Issue 4, May 2011, Pages 811–820