ABSTRACT. Un programme quadratique en variables binaires possède des propriétés très particulières. Il peut être linéarisé, c’est à dire reformulé en un programme linéaire en variables binaires, par augmentation du nombre de variables. Il peut aussi être convexifié, c’est à dire reformulé en un programme quadratique convexe en variables binaires, par un simple calcul de valeur propre extrême. Qu’il soit linéarisé ou convexifié, le problème reformulé peut alors être résolu par un Branch-and-Bound basé sur la relaxation continue. Ces deux paradigmes sont connus depuis plusieurs décennies mais aucun des deux ne permet d’obtenir efficacement l’optimum, en dehors d’instances de petite taille ou de faible densité. Nous montrons que la Reformulation Quadratique Convexe permet de mettre en commun les deux paradigmes pour les renforcer tous les deux et autoriser la résolution exacte de bien plus larges instances. Nous étendons ensuite cette approche au cas où les variables sont des entiers ou des réels dans un intervalle. Nous montrons qu’elle peut également s’appliquer à l’optimisation polynomiale en variables binaires, après une phase de quadratisation. Enfin, nous reportons l’utilisation de cette approche à un problème d’Optimisation de Flux de Puissances dans un réseau de transport de l’électricité.

ABSTRACT. Les algorithmes de recherche locale se basent sur une évolution de la solution courante au moyen d'un guidage par une fonction d'évaluation. Usuellement, cette fonction d'évaluation est ou découle directement de la fonction objectif du problème. Les difficultés de résolution apparaissent alors lorsque le paysage de recherche naturellement induit par l'instance de problème n'est pas parfaitement exploitable, présente un certain niveau de rugosité et donc comporte de nombreux optimums locaux. Nous proposons ici de déplacer la problématique de la recherche d'une solution, à celle de la recherche d'un algorithme dont le guidage serait effectué par une fonction d'évaluation à déterminer.

ABSTRACT. Multistage Stochastic Programming consists in minimizing the expected cost of some decision over a set of coupled scenarios. Progressive Hedging is a popular strategy for solving such problems, based on scenario decomposition. In this talk, we present a randomized version of this algorithm able to compute an update as soon as a scenario subproblem is solved. This is of crucial importance when run on parallel computing architectures. We prove that the randomized version has the same converge properties as the standard one and we release an easy-to-use Julia toolbox.

ABSTRACT. L'approximation parcimonieuse consiste à ajuster un modèle au sens des moindres carrés avec un faible nombre de composantes non nulles (la "norme" l_0). Ce problème revient à considérer un programme mixte en nombres entiers avec des contraintes de binarité. Nous proposons un algorithme de type Branch-and-Bound pour l'exploration des variables binaires. Nous montrons que l'évaluation de chaque noeud par relaxation continue peut être réalisée en résolvant des problèmes en norme l_1 avec des contraintes de borne, pour lequel nous construisons un algorithme spécifique. La méthode résultante s'avère plus efficace que le solveur générique CPLEX, notamment lorsque la dimension du problème augmente.

ABSTRACT. Generating the true Pareto front of mixed-integer linear programming problems is challenging, especially if the goal function is simultaneously dependent on continuous and discrete variables. A new method is presented to overcome the limitations tied to epsilon-constrained  and weighted sum approaches. The method is based on reductions to single-objective MILP models that generate an incumbent front and refine it until the true (optimal) Pareto front is obtained. The method is tested on an assembly line balancing-sequencing problem variant. Challenges and perspectives are discussed.

ABSTRACT. In this tutorial, we aim at surveying the fundamentals of theoretical and practical aspects of mixed integer non linear programming (MINLP). MINLPs are very powerful and challenging optimization problems that can represent an extremely large variety of real-world applications. After basic theoretical notions, we focus on algorithms for MINLPs. Finally, some practical tools for MINLPs are presented.

ABSTRACT. Le contrôle du trafic aérien vise à garantir le respect de normes de séparation entre les usagers de l'espace aérien. Dans un contexte d'augmentation constante du trafic mondial, l'automatisation et l'aide à la décision représentent deux enjeux majeurs du domaine. Lors de ce tutoriel je dessinerai un panorama des méthodes de programmation mathématique pour le contrôle du trafic aérien. Dans le cas déterministe, une famille de modèles formule explicitement la physique du vol et les distances de séparation, tandis que d'autres discrétisent l'espace des manoeuvres d'évitement pour abstraire la situation à l'aide d'un graphe de conflits. La seconde partie de l'exposé élargira la discussion à la prise en compte des incertitudes, facteur essentiel pour capturer la réalité des pratiques des contrôleurs. La présentation s'orientera alors vers une approche multi-objectif avant de s'ouvrir vers la programmation stochastique.

ABSTRACT. Ce tutoriel présentera les principes fondamentaux de la résolution et de la modélisation en programmation par contraintes (PPC). Il est destiné à un public sans aucune connaissance préalable en PPC et peut servir à découvrir complètement ce domaine. On s’intéressera en particulier aux cohérences locales (l'arc-cohérence et la bornes-cohérence) qui seront expliquées en détail comme des propriétés des domaines des variables. On se penchera ensuite sur les algorithmes de filtrage permettant de les obtenir en essayant d'illustrer différentes techniques algorithmiques et de souligner les liens avec la recherche opérationnelle (RO). Dans une dernière partie, nous ferons le point sur le travail de modélisation en PPC en essayant de le mettre en perspective avec la modélisation en programmation linéaire.

ABSTRACT. L'optimisation robuste (OR) est un des paradigmes disponibles actuellement pour traiter les problèmes de recherche opérationnelle intégrant de l'incertitude sur les données. Dans ces problèmes, une partie des décisions doivent être prises en ayant seulement une connaissance imprécise de certains paramètres. L'OR se caractérise par une modélisation de l'incertitude sous forme d'un ensemble de scénarios de données plausibles (souvent de taille infinie et décrit implicitement). On recherche alors une solution réalisable pour chacune de ces éventualités, et dont la valeur - dans le pire des cas - est la meilleure possible. L'objectif de la présentation est de présenter les modèles et méthodes de résolution de base reposant sur la programmation linéaire (en nombres entiers), avec leurs avantages et inconvénients. Ces techniques seront illustrées sur des applications en planification et ordonnancement

ABSTRACT. Après quelques rappels sur les chaînes de Markov, nous présenterons les principes fondamentaux des processus de décision markovien ainsi que les liens avec l'apprentissage par renforcement. Dans un processus de décision markovien, un agent observe l'état d'un système et choisit une action parmi celles disponibles. Suite à son action, le système évolue vers un autre état de manière probabiliste et obtient une récompense. Ce processus est réitéré un certain nombre de fois, l'objectif de l'agent étant de maximiser ses gains (en espérance). Si le processus s'achève lorsqu'un état terminal est atteint, on parle de plus court chemin stochastique. Lorsque les récompenses et probabilités de transition sont inconnues et découvertes au fil de l'eau, on rentre dans le paradigme de l'apprentissage par renforcement.

ABSTRACT. L’intelligence artificielle est partout en ce moment: les médias en parlent, nos universités l’affichent, la communauté scientifique la met à l’honneur. Dans ce tutoriel, nous discuterons des interactions entre intelligence artificielle et recherche opérationnelle, au sens large. Nous présenterons les idées de base de l’apprentissage, en insistant sur le rôle de l’optimisation stochastique.  Nous ferons quelques coups de projecteurs sur des problématiques récentes: comment atteindre de bons équilibres dans un jeu génératif (comme les GANs) ? comment apprendre collectivement un modèle sans manipuler de données personnelles (comme le federated learning de Google avec nos téléphones portables) ? Nous insisterons sur les grandes idées et les exemples, sans entrer dans les détails techniques.