Search

In this paper, we propose a reactive local search-based algorithm for the disjunctively, constrained knapsack problem (DCKP). DCKP is a variant of the standard knapsack problem, an NP-hard combinatorial optimization problem, with special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item is packed. The proposed algorithm is based upon a reactive local search, where an explicit check for the repetition of configurations is added to the search process. Initially, two complementary greedy procedures are applied in order to construct a starting solution. Second, a degrading procedure is introduced in order (i) to escape to local optima and (ii) to introduce a diversification in the search space. Finally, a memory list is added in order to forbid the repetition of configurations. The performance of two versions of the algorithm has been evaluated on several problem instances and compared to the results obtained by running the Cplex solver. Encouraging results have been obtained. doi:10.1057/palgrave.jors.2602046 Published online 24 August 2005 Keywords: combinatorial optimization: heuristics: knapsacks: reactive local search

In this paper, we propose several heuristics for approximately solving the multiple-choice multidimensional knapsack problem (noted MMKP). an NP-Hard combinatorial optimization problem. The first algorithm is a constructive approach used especially for constructing an initial feasible solution for the problem. The second approach is applied in order to improve the quality of the initial solution. Finally, we introduce the main algorithm, which starts by applying the first approach and tries to produce a better solution to the MMKP. The last approach can be viewed us a two-stage procedure: (i) the first stage is applied in order to penalize a chosen feasible solution and, (ii) the second stage is used in order to normalize and to improve the solution given by the firs stage. The performance of the proposed approaches has been evaluated based problem instances extracted from the literature. Encouraging results have been obtained. Keywords: combinatorial optimization: guided local search: heuristic, knapsack