 A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack ProblemPost-Print from HAL Abstract: 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 \in \mathcal P=\{1,\ldots,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 algorithms: (i) a limited-area local search applied in the elite neighborhood and which accepts the first solution with some deterioration threshold of the current 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 problem instances obtained by a generator code taken from the literature. The tests were executed in compeltely comparable scenarios to those of the literature. The results are promising and the efficiency of the proposed approach is also shown. Keywords: Combinatorial optimization; Knapsack; Max-Min optimization; Robust optimization; Heuristics; Cooperative (search for similar items in EconPapers) Published in European Journal of Operational Research, 2009, 202 (2), pp.339-346. ⟨10.1016/j.ejor.2009.05.033⟩ Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00644088 DOI: 10.1016/j.ejor.2009.05.033 Access Statistics for this paper More papers in Post-Print from HAL |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.