This paper addresses a Lagrangian heuristic-based neighborhood search for the multiple- choice multi-dimensional knapsack problem, an NP-hard combinatorial optimization problem. The problem is solved by using a cooperative approach that uses a local search for exploring a series of neighborhoods induced from the Lagrangian relaxation. Each neighborhood is submitted to an optimization process using two alternative strategies: reducing and moving strategies. The reducing strategy serves to reduce the current search space whereas the moving strategy explores the new search space. The performance of the proposed approach is evaluated on benchmark instances taken from the literature. Its obtained results are compared to those reached by some recent methods available in the literature. New solutions have been obtained for almost 80% of the instances tested.
Keywords: Knapsack; Lagrangian relaxation; neighbourhood; optimization.
Mhand Hifi and Lei Wu
doi:10.1080/0305215X.2014.982631
A version on ResearchGate: source
Benchmark instances:
download (I1-13 and INST01-20), download (instance1-256)
991total visits.