| Popis: |
LocalSolver is a mathematical programming solver.Originally designed to solve large scale combinatorial optimization problems such as those found in the industry, it mainly relies on local search heuristics.This pragmatic solution approach, coupled with expressive nonlinear and set-based modeling techniques, has allowed LocalSolver to establish itself as a successful commercial solver.The purpose of this thesis is to implement a complementary dual approach for the computation of lower bounds within LocalSolver.The main stake is to qualify the solutions found by the solver and to potentially prove their optimality, thus allowing an early stop of the search.Furthermore, lower bounds have many other applications, such as the detection of inconsistent problems.This is useful in the development phase where modeling errors are frequent.We face three major challenges.First, the problems we address are generic and can be combinatorial, nonlinear or even nonsmooth.Then, the integration to an industrial software requires to produce reliable and high-quality code that can scale in time and memory.Finally, any reformulation need must be managed in-house, to allow LocalSolver's users to model their problems in the easiest way possible.The dual module provided to LocalSolver starts by reformulating the given optimization problem into a mixed-integer nonlinear program (MINLP).This program is stored under a standard form that facilitates the implementation of various techniques aiming at computing lower bounds.Examples of such techniques are the generation of convex relaxations, bound tightening techniques and presolve actions.These building blocks are then integrated into a partitioning scheme called the branch-and-reduce algorithm, and interact with the primal modules thanks to concurrent computing techniques.While this approach remains traditional, several choices and implementation features vary from the state of the art.The operators we support and the reformulation technique we use allow us to compute lower bounds on more problems than most global optimization solvers.These solvers also mainly use linear relaxations, whereas our goal is to show that nonlinear relaxations can be competitive.For this purpose, we implement a nonlinear solver dedicated to the computation of lower bounds to our convex relaxations.At last, we establish a duality result under bound constraints that allow us to improve the performance of our custom nonlinear solver.It is also exploited to certify the validity of the lower bounds computed by LocalSolver and to obtain robust inconsistency certificates.; 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. |
