Exploiting structure in Mixed-Integer Linear and Non-linear Programming

La programmation mathématique en nombres entiers (PNE), par son caractère générique, permet de formuler de nombreux problèmes de décision de la vie réelle. Ainsi, les outils de PNE sont utilisés quotidiennement pour, par exemple, fabriquer des horaires de personnel ou des itinéraires de véhicules de livraison, opérer des réseaux électriques, gérer des inventaires, ou encore décider de politiques d'investissement. Ce succès est, en grande partie, rendu possible par le développement, au cours des dernières décennies, d'outils logiciels robustes et performants, capables de résoudre efficacement un grand nombre de problèmes pratiques. Toutefois, l'amélioration de tels outils s'est accompagnée d'une augmentation de la diversité, taille et complexité des problèmes que les praticiens cherchent à résoudre, dépassant parfois les capacités des principaux solveurs de PNE. Dans ce contexte, l'objectif de cette thèse est le développement d'algorithmes spécialisés, i.e., qui exploitent la structure mathématique d'une classe de problèmes donnée, et leur intégration au sein du cadre algorithmique de la PNE. Ce travail explore ainsi une voie hybride entre solveurs PNE génériques et spécialisés, et se situe à l'intersection entre la conception d'algorithmes de PNE, et leur implémentation pratique. Tout d'abord, nous proposons une formulation PNE pour la gestion d'un réseau électrique comprenant de multiples ressources énergétiques distribuées. Étant donnés la structure du réseau et certains enjeux de respect de la vie privée, le problème est reformulé par décomposition de Dantzig-Wolfe, et résolu par un algorithme de génération de colonnes. Cette approche est générique, i.e., n'importe quel type de ressource peut être pris en compte, et efficace. En effet, des tests numériques montrent que des systèmes comportant plusieurs milliers de ressources peuvent être résolus à l'optimalité. Ensuite, nous présentons la conception algorithmique et l'implémentation de Tulip, un solveur de programmation linéaire basé sur un algorithme de points intérieurs. Plus spécifiquement, le code de Tulip est structuré de façon à permettre l'utilisation de librairies d'algèbre linéaire spécialisées, qui peuvent être implémentées directement par l'utilisateur. Plusieurs tests numériques démontrent l'efficacité du code, tant pour des instances non-structurées que présentant une certaine structure. Dans le premier cas, la performance de Tulip est comparable à celle de solveurs en source libre. Dans le second, l'utilisation de routines spécialisées améliore la performance d'un facteur 10, et rend Tulip compétitif avec les meilleurs solveurs commerciaux. Enfin, nous étudions les aspects pratiques de plans coupants disjonctifs pour l'optimisation conique en variables mixtes. En nous appuyant sur la dualité conique, nous formulons un programme d'optimisation conique pour séparer de tels coupes, et analysons les aspects théoriques de plusieurs normalisations. De plus, nous mettons en lumière certaines difficultés rencontrées dans le cadre d'algorithmes d'approximation polyhédrale, et proposons des extensions à plusieurs techniques initialement proposées dans le contexte linéaire. L'efficacité de notre approche est validée à travers plusieurs expériences numériques, et est compétitive avec la génération de coupes par le solveur CPLEX.