Optimisation globale avec LocalSolver

LocalSolver est un logiciel de programmation mathématique.Originellement pensé pour traiter les grands problèmes d’optimisation combinatoire rencontrés dans l’industrie, son fonctionnement repose sur des heuristiques de recherche locale.Cette approche de résolution pragmatique, couplée à des structures de modélisation expressives, non linéaires et ensemblistes, lui ont permis de s'imposer dans le catalogue des solveurs commerciaux.L'objet de cette thèse est le développement d'une approche duale, complémentaire à la recherche locale, qui fournira des bornes aux problèmes traités.L'intérêt principal est de qualifier la qualité des solutions retournées, voire de prouver leur optimalité, permettant ainsi d'interrompre plus rapidement la résolution.Ce n'est cependant pas le seul, puisque les techniques nécessaires au calcul de bornes permettent par exemple de prouver l'inconsistance d'un problème.Cette fonctionnalité est utile en phase de développement, où des erreurs de modélisation ou de données sont fréquentes.Trois difficultés principales se présentent alors.D'abord, les problèmes traités sont génériques, et peuvent être combinatoires, non linéaires ou encore non différentiables.Ensuite, l'intégration à un logiciel industriel impose un haut niveau de fiabilité et de qualité logicielle, ainsi que la capacité à passer à l'échelle en temps et en mémoire.Enfin, tous les besoins de reformulation doivent être pris en compte en interne, afin de permettre aux utilisateurs de LocalSolver de modéliser leurs problèmes le plus naturellement possible.Ainsi, le module dual implémenté au sein de LocalSolver commence par transformer le problème d'optimisation fourni en un programme non linéaire en variables mixtes (MINLP).Ce programme est représenté sous une forme standard facilitant l'implémentation de divers outils utiles au calcul de bornes : génération de relaxations convexes, techniques de réduction de bornes ou encore actions de emph{presolve}.Ces outils sont ensuite intégrés dans une recherche arborescente de type emph{branch-and-reduce}, qui interagit avec les autres modules de LocalSolver grâce à des techniques de programmation concurrente.Si l'approche décrite ci-dessus est classique, plusieurs spécificités et choix d'implémentation se différentient de l’état de l’art.En effet, les opérateurs mathématiques supportés et la technique de reformulation utilisée permettent de calculer des bornes sur plus de problèmes que les solveurs d'optimisation globale de référence.Ensuite, ces solveurs exploitent principalement des relaxations linéaires, alors que l'un de nos objectifs est de montrer que des relaxations non linéaires peuvent être compétitives.Dans cette optique, nous avons implémenté un solveur non linéaire sur-mesure, dédié au calcul de bornes inférieures d'un problème convexe, et adapté aux relaxations non linéaires utilisées.Enfin, un résultat de dualité sous contraintes de bornes est obtenu.Celui-ci permet d'améliorer la performance du solveur non linéaire et d'y inclure une méthode robuste de détection de l'inconsistance, mais aussi de garantir la fiabilité des bornes inférieures calculées par LocalSolver.