Stage de Master 2 proposé à l'Ecole des Ponts - LIGM Equipe Imagine
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 aussi sensible aux choix de variable à bissecter et au
choix du prochain noeud.
Si la stratégie en meilleur d'abord est souvent utilisée, elle ne guide pas la recherche vers l'obtention d'un point faisable. Or, cela peut accélérer la recherche en propageant la contrainte de trouver une meilleure valeur de la fonction à optimiser.
Objectif du stage
L'objectif du stage sera d'étudier la prise en compte des contraintes dans une stratégie de choix du noeud à traiter.
Il s'agira d'abord réaliser une étude bibliographique sur les différentes méthodes de choix de noeud existantes, en particulier pour les problèmes d'optimisation globale non convexe avec contraintes.
Puis, on cherchera à définir de nouvelles stratégies de choix du noeud courant dans l'algorithme du Branch and Bound pour trouver des bonnes solutions faisables. Ces stratégies seront implantées dans la bibliothèque logicielle Ibex en C++ et testées sur une base de
problèmes tests.
Profil
Connaissances en algorithmique, C++, optimisation combinatoire
Contact
Bertrand Neveu
Bertrand.Neveu@enpc.fr 0164152175
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
M.Cs. Markot,J. Fernandez,L.G. Casado,T. Csendes
New interval methods for constrained global optimization
Math. Program., Ser. A 106, 287–318 (2006)
Bertrand Neveu, Gilles Trombettoni, and Ignacio Araya
Node Selection Heuristics Using the Upper Bound in Interval Branch and Bound
MAGO'14, XII Global Optimization Workshop, Malaga, Spain, sept 2014
P Belotti, J. Lee, L. Liberti, F. Margot, and A. Waechter.
Branching and bounds tightening techniques for non-convex MINLP.
Optimization Methods and Software,24(4-5):597–634, 2009.
Mohit Tawarmalani, Nikolaos V. Sahinidis
Global optimization of mixed-integer nonlinear programs: A theoretical and
computational study
Mathematical Programming, April 2004, Volume 99, Issue 3, pp 563-591