The Multi-scenario Knapsack Problem: An Adaptive Search Algorithm
| Main Authors: | Mhand Hifi, Hedi Mhalla, Mustapha Michaphy |
|---|---|
| Format: | Article eJournal |
| Bahasa: | eng |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
https://zenodo.org/record/1076614 |
Daftar Isi:
- In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.