Jour : 16 mars 2016

In this paper, we investigate the use of a hybrid guided neighborhood search for solving the disjunctively constrained knapsack problem. The studied problem may be viewed as a combination of two NP-hard combinatorial optimization problems: the weighted-independent set and the classical binary knapsack. The proposed algorithm is a hybrid approach that combines both deterministic and random local searches. The deterministic local search is based on a descent method, where both building and exploring procedures are alternatively used for improving the solution at hand. In order to escape from a local optima, a random local search strategy is introduced which is based on a modified ant colony optimization system. During the search process, the ant colony optimization system tries to diversify and to enhance the solutions using some informations collected from the previous iterations. Finally, the proposed algorithm is computationally analyzed on a set of benchmark instances available in the literature. The provided results are compared to those realized by both the Cplex solver and a recent algorithm of the literature. The computational part shows that the obtained results improve most existing solution values.

Keywords: Combinatorial optimization; hybridation; integer programming; knapsack; neighborhood.

Mhand Hifi, Sagvan Saleh, Lei Wu

doi:10.1080/23311916.2015.1068969

Benchmark instances: download

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)