Problèmes d'optimisation combinatoire : évaluation de méthodes de la physique statistique / Bertrand Cabon ; sous la direction de Paul Bourret

Date :

Editeur / Publisher : [S.l.] : [s.n.] , [1996]

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Recuit simulé (mathématiques)

Optimisation combinatoire

Mécanique statistique

Bourret, Paul (19..-.... ; informaticien) (Directeur de thèse / thesis advisor)

École nationale supérieure de l'aéronautique et de l'espace (Toulouse ; 1972-2007) (Organisme de soutenance / degree-grantor)

Relation : Problèmes d'optimisation combinatoire : évaluation de méthodes de la physique statistique / Bertrand Cabon ; sous la direction de Paul Bourret / Grenoble : Atelier national de reproduction des thèses , 1996

Résumé / Abstract : Nous abordons dans cette thèse trois approches pour la résolution de problèmes combinatoires difficiles. Nous montrons comment les méthodes du Recuit Simulé et de l'Approximation de Champ Moyen, issues de la Physique Statistique, peuvent être utilisées pour résoudre des problèmes d'optimisation discrète. Nous présentons également, dans le cadre CSP (Constraint Satisfaction Problems), des méthodes exactes de résolution sur le principe du "Branch and Bound". Les comportements de ces approches sont comparés sur différents problèmes combinatoires difficiles tels que le recalage d'images satellites, le problème d'allocation de f'équences radio, ou des problèmes CSP aléatoires. Enfin, nous montrons comment la méthode du Champ Moyen peut accélérer une méthode de type Branch and Bound en lui fournissant une bonne affectation initiale et deux heuristiques d'ordonnancement des variables et des valeurs. Nous présentons des résultats expérimentaux sur des problèmes CSP générés aléatoirement.