Combining Resolution Search and Dynamic Programming for the 0-1 Multidimensional Knapsack Problem
| Autor: | Vasquez, Michel, Boussier, Sylvain, Hanafi, Said, Vimont, Yannick, Wilbaut, Christophe |
|---|---|
| Přispěvatelé: | Laboratoire de Génie Informatique et Ingénierie de Production (LGI2P), IMT - MINES ALES (IMT - MINES ALES), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire Informatique d'Avignon (LIA), Avignon Université (AU)-Centre d'Enseignement et de Recherche en Informatique - CERI, Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201 (LAMIH), Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Centre National de la Recherche Scientifique (CNRS)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France) |
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: | |
| Zdroj: | IFORS 2011-International Federation of Operational Research Societies International Federation of Operational Research Societies International Federation of Operational Research Societies, Jul 2011, Australia |
| Popis: | International audience; We propose an exact method which combines resolution search, branch and bound, and dynamic programming algorithm for solving the 0-1 Multidimensional Knapsack Problem. Our method is a multi-level search strategy where the top level branches of the search tree are enumerated using Resolution Search, the middle level branches are enumerated using Branch & Bound and the lower level branches are solved with dynamic programming. The proposed algorithm is competitive with the existing heuristics in terms of convergence and is able to prove large-scale strong correlated instances of the OR-Library |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|