PMNL: Programmation mathématique non linéaire

Animateurs: 
Claudia d’AmbrosioLIXPalaiseaudambrosio@lix.polytechnique.fr
Sonia CafieriENACToulousesonia.cafieri@enac.fr
Amélie LambertCEDRICParisamelie.lambert@cnam.fr
Frédéric MessineLAPLACEToulousefrederic.messine@laplace.univ-tlse.fr
Frédéric RoupinLIPNVilletaneuseFrederic.Roupin@lipn.univ-paris13.fr
Gilles TrombettoniLIRMMMontpelliergilles.trombettoni@lirmm.fr
Groupes de Travail (GdT): 

Cet axe ne comporte pas de Groupe de Travail

Description de l'axe: 

La recherche en optimisation non-linéaire s'est d'abord focalisé sur les problèmes continus (où les variables sont réelles). Les méthodes numériques se sont d'abord développés pour trouver des optima locaux. Plus récemment, des méthodes déterministes d'optimisation globale ont été développées. Elles sont principalement basées sur des algorithmes de Branch and Bound.

D'autre part, après de nombreuses années principalement dédiées à la résolution de problèmes d’optimisation  linéaire, l’optimisation non-linéaire en variables mixtes entières (MINLP pour Mixed Integer Nonlinear Programming) est maintenant un domaine de recherche très actif. Cette discipline fournit un cadre pour la modélisation et la résolution de nombreux problèmes réels dans des domaines d’application variés comme les télécommunications, l’énergie, la finance, la physique, ou l’ingénierie. Bien que des progrès significatifs aient été réalisés dans les deux dernières décennies, il y a toujours de nombreux verrous théoriques et pratiques provenant des difficultés croissantes des problèmes à résoudre, à la fois en terme de nature intrinsèque du problème, mais aussi du point de vue du passage à l’échelle.

Ainsi, notre axe de recherche porte sur la résolution de problèmes non-linéaires en variables entières, continues et mixtes. Les MINLPs sont de plus en plus étudiés et nous souhaitons les privilégier dans cet axe. Plus formellement, les MINLPs consistent à optimiser une fonction non-linéaire dans une région réalisable décrite par des fonctions non-linéaires et où certaines des variables sont contraintes à prendre des valeurs entières. Ces problèmes combinent deux difficultés : la nature combinatoire de leurs variables entières et la non-convexité de leurs fonctions (objectif et contraintes). Les approches classiques de résolution à l’optimum global traitent les deux difficultés séparément. L’intégrité des variables est gérée par des méthodes classiques de branch-and-bound. Et, pour contourner la non-convexité, le principe est de calculer une relaxation convexe du problème de départ qui fournira une borne (inférieure en cas de minimisation). Cette borne peut être de plusieurs natures : linéaire, quadratique et convexe, semi-définie positive, où issue de la programmation conique par exemple, et est classiquement utilisée dans un algorithme de branch-and-bound dit « spatial ». La différence avec un branch-and-bound classique est que le branchement est effectué sur les variables continues, mais le principe reste le même : partitionner récursivement l’espace de recherche en deux sous-problèmes, où pour chacun une borne convexe est calculée. Des solveurs stables implémentant des branch-and-bounds spatiaux basées sur des bornes linéaires sont disponibles, cependant, sans aucune hypothèse sur les fonctions, même pour des instances de petites tailles la résolution à l’optimum global reste encore difficile.