Academic Journal
A Cooperative . . . for the Multiple-Scenario Max-Min Knapsack Problem
| العنوان: | A Cooperative . . . for the Multiple-Scenario Max-Min Knapsack Problem |
|---|---|
| المؤلفون: | Abdelkader Sbihi |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://hal-audencia.archives-ouvertes.fr/docs/00/64/40/88/PDF/msm2kp_ejor.pdf. |
| سنة النشر: | 2009 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | Key words, Combinatorial optimization, Knapsack, Max-min optimization, Robust optimization, Heuristics, Cooperative |
| الوصف: | The purpose of this article is to present a novel method to approximately solve the Multiple-Scenario Max-Min Knapsack Problem (MSM2KP). This problem models many real world situations, e.g. when for many scenarios noted pi ∈ P = {1,., P}, the aim is to identify the one offering a better alternative in term of maximizing the worst possible outcome. Herein is presented a cooperative approach based on two local search algo-rithms: (i) a limited-area local search applied in the elite neighborhood and which accepts the first solution with some deterioration threshold of the cur-rent solution, (ii) a wide range local search is applied to perform a sequence of paths exchange to improve the current solution. Results have been analyzed by means state-of-the art methods and via prob-lem instances obtained by a generator code taken from the literature. The tests were executed in compeltely comparable scenarios to those of the liter-ature. The results are promising and the efficiency of the proposed approach is also shown. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.636.1323; http://hal-audencia.archives-ouvertes.fr/docs/00/64/40/88/PDF/msm2kp_ejor.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.636.1323 http://hal-audencia.archives-ouvertes.fr/docs/00/64/40/88/PDF/msm2kp_ejor.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.9F5FF2E5 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |