Le 05/02/2014 par bneveu :
Stage de Master 2 proposé à l'Ecole des Ponts - LIGM
Titre
Traitement automatique d'heuristiques de bissection pour l'optimisation globale
Contexte
L'optimisation globale d'une fonction non linéaire sous des contraintes
non linéaires, c-à-d trouver le minimum global de cette fonction
continue définie sur un pavé de R^n, est en général un problème NP-difficile pour lequel il n'existe pas d'algorithme polynomial pour le résoudre.
L'algorithme complet le plus utilisé est l'algorithme de
séparation-évalauation (Branch and Bound), qui construit un arbre de
recherche, en coupant les domaines des variables. Les principales
recherches dans ce domaine ont été menées sur les linéarisations et les
techniques de propagation, mais la performance est très sensible aux
choix de variable à bissecter. Il existe pour celà des heuristiques de
bissection générales et le choix d'une bonne heuristique est crucial.
Ce choix pour les branchements existe aussi dans la résolution de
problèmes discrets, comme l'optimisation combinatoire ou les problèmes
de satisfaction de contraintes, pour lesquels il existe aussi des
heuristiques de branchement. Le choix a priori d'une heuristique peut
aboutir à des résultats désastreux.
Objectifs
Pour rendre la résolution plus robuste, nous avons dévéloppé plusieurs méthodes
pour gérer des heuristiques qui sélectionnent les variables à couper ou
affecter. Certaines de ces méthodes sont basées sur des redémarrages, sur la
gestion d'un portefeuille d'heuristiques, sur un prétraitement et un
apprentissage au début de l'arbre de recherche, et d'autres enfin sur un
mélange et des choix en partie aléatoires.
L'objectif de ce stage est d'étudier ces méthodes, de sélectionner et
d'adapter l'une d'elles au cas continu, où les domaines des variables
sont des intervalles bornés. Cette méthode sera codée dans la
bibliothèque C++ Ibex, un résolveur de problèmes de contraintes
continues et testé sur des problèmes d'optimsation globale du banc d'essai COCONUT.
Profil
Connaissances en algorithmique, C++, optimisation combinatoire
Références
G. Trombettoni, I. Araya, B. Neveu, G. Chabert
Inner Regions and Interval Linearizations for Global Optimization
Proc. of AAAI 2011, pages 99-104, San Francisco, CA, USA
C. Gomes. Complete randomized backtrack search (survey). In M. Milano, editor,
Constraint and Integer Programming: Toward a Unified Methodology, pages 233
283. Kluwer, 2003.
L.Granvilliers Adaptive bisection of Numerical CSPs, Principles and Practice of Constraint Programming
CP 2012, Springer Lecture Notes in Computer Science 2012, pp 290-298
Contact
Bertrand Neveu Bertrand.Neveu@enpc.fr 0164152175
