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.

Abstract

The past 70 years have witnessed tremendous performance improvements of algorithms and software for mixed-integer programming. These developments have been met by a likewise increase in the size and complexity of the models that practitioners aim to solve: there is no shortage of challenging problems. In that context, this thesis investigates the use of structure-exploiting techniques within generic optimization paradigms, to tackle large-scale or otherwise intractable instances. In particular, we build on the observation that structureexploiting techniques can often be viewed as specialized implementations of one or several individual components of generic MIP algorithms. First, we consider the coordination of Distributed Energy Resources in power systems. This problem is first formulated as a centralized –but intractable– mixed-integer linear program, then reformulated using Dantzig-Wolfe decomposition and solved by a column-generation algorithm. The proposed framework is generic, i.e., it can handle resources of arbitrary nature, and computationally efficient: problems with thousands or resources are solved to proven optimality in less than an hour. Finally, besides scalability, the decomposition scheme naturally addresses some privacy concerns regarding the operation of individual resources. Second, we focus on structure-exploiting interior-point methods for linear programming. To that end, we develop an open-source interior-point solver, Tulip, whose algorithmic framework is disentangled from linear algebra implementations. This flexible design allows to easily integrate specialized, user-provided linear algebra routines. Through various numerical experiments, we demonstrate the flexibility, efficiency and robustness of the code. Finally, we investigate the separation of disjunctive cutting planes in mixed-integer conic programming, and demonstrate the benefits of exploiting a problem's conic structure. Leveraging conic duality, the separation of disjunctive cuts is formulated in a single cut-generating conic problem (CGCP); this dual perspective offers a number of insights that were unavailable to previous approaches. In particular, we study the theoretical and computational merits of several normalization conditions, including the loss of strong conic duality in the separation problem, and the separation of conic-infeasible points in the context of outer-approximation algorithms. Computational experiments demonstrate the efficiency of the proposed approach on several classes of instances.