Nora Touati

Décomposition et résolution de problèmes d'optimisation de grande taille

De nombreux secteurs économiques (télécommunication, transport, ...) ou
non (développement durable), sont confrontés à des problèmes
d'optimisation de plus en plus grands. Ces problèmes se placent hors des
capacités de résolution effective des logiciels disponibles aujourd'hui,
même les plus spécialisés. Pour pouvoir les traiter, des méthodes de
décomposition de l'espace des solutions sont utilisées. Nous
présenterons quelques techniques de décomposition et les liens existants
entre certaines d'entre elles.

La décomposition engendre souvent des problèmes avec un très grand
nombre de variables, d'où un intérêt croissant pour les méthodes de type
génération de colonnes dont le point fort est de pouvoir caractériser
une solution optimale d'un problème en manipulant un ensemble réduit de
ses variables. Nous présenterons les points forts et faibles de cette
méthode et proposerons quelques améliorations.