Amélioration des solutions intermédiaires pour la résolution exacte du sac à dos multidimensionnel en 0–1
| Autor: | Boussier, Sylvain, Vasquez, Michel, Vimont, Yannick |
|---|---|
| Přispěvatelé: | Vasquez, Michel, Laboratoire Informatique d'Avignon (LIA), Centre d'Enseignement et de Recherche en Informatique - CERI-Avignon Université (AU), 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) |
| Jazyk: | francouzština |
| Rok vydání: | 2009 |
| Předmět: |
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
variables binaires resolution search sac à dos multidimensionnel [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] |
| Popis: | Nous nous intéressons à la résolution exacte du sac à dos multidimensionnel en 01 qui est un problème classique d'optimisation combinatoire. Dans de précédents travaux (Boussier et al. (2008) [1]), nous avons présenté une méthode exacte de résolution du MKP combinant Resolution search (Chvátal (1997) [3]) avec un algorithme d'énumération implicite (Vimont et al. (2008) [4]). Cette méthode est globalement plus performante que les méthodes exactes connues sur un grand nombre d'instances de la OR-Library. Elle résout la plupart des instances en un temps plus rapide et prouve l'optimalité d'instances dont l'optimum était inconnu jusqu'à présent. Les solutions intermédiaires qu'elle génère ne sont pourtant pas toujours compétitives avec celles produites par les meilleures heuristiques existantes. Dans cette présentation, nous détaillons la méthode proposée dans [1] et présentons une technique d'amélioration de la génération des solutions intermédiaires permettant d'obtenir de bonnes solutions plus rapidement. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|