In this paper a fast large neighborhood search-based heuristic is proposed for solving the Disjunctively Constrained Knapsack Problem (DCKP). The proposed method combines a two-phase procedure and a large neighborhood search. First, a two-phase procedure is applied in order to construct a starting feasible solution of the DCKP. Its first phase serves to determine a feasible solution by combining two complementary problems: the weighted independent set problem and the classical binary knapsack problem. Its second phase uses a descent method trying to improve the current solution by applying both degrading and re-optimizing strategies. Second, a large neighborhood search is used for diversifying the search space. Finally, the performance of the proposed method is computationally analyzed on a set of benchmark instances for the literature and its results are compared to those reached by both Cplex solver and more recent algorithms in the literature. Several improved solutions have been obtained within small average runtime.
Keywords: Heuristic; knapsack; neighborhood; re-optimisation.
Mhand Hifi, Sagvan Saleh, Lei Wu
doi:10.1007/978-3-319-09174-7_34
A version on ResearchGate: source
Benchmark instances: download (I1-13 and INST01-20)
2139total visits.