Les problèmes d'optimisation discrète sont pour beaucoup difficiles à résoudre, depar leur nature combinatoire. Citons par exemple les problèmes de programmationlinéaire en nombres entiers. Une approche couramment employée pour les résoudreexactement est l'approche de Séparation et Évaluation Progressive. Une approchedifférente appelée " Resolution Search " a été proposée par Chvátal en 1997 pourrésoudre exactement des problèmes d'optimisation à variables 0-1, mais elle restemal connue et n'a été que peu appliquée depuis.Cette thèse tente de remédier à cela, avec un succès partiel. Une première contributionconsiste en la généralisation de Resolution Search à tout problème d'optimisationdiscrète, tout en introduisant de nouveaux concepts et définitions. Ensuite,afin de confirmer l'intérêt de cette approche, nous avons essayé de l'appliquer enpratique pour résoudre efficacement des problèmes bien connus. Bien que notrerecherche n'ait pas abouti sur ce point, elle nous a amené à de nouvelles méthodespour résoudre exactement les problèmes d'affectation généralisée et de localisationsimple. Après avoir présenté ces méthodes, la thèse conclut avec un bilan et desperspectives sur l'application pratique de Resolution Search.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00968201 |
| Date | 03 February 2012 |
| Creators | Posta, Marius |
| Publisher | Université d'Avignon |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0021 seconds