|
|
|
Programme > Videos des présentationsSessions plénières
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é..
There is much hype surrounding quantum computing and its potential applications for optimization. However, the technical details are often lost in translation. This talk provides an overview of quantum algorithms that could potentially be useful for continuous or discrete optimization. Most of the discussion will be devoted to the benefits and limitations of algorithms for SDP and LP via faster solution of linear systems, or with the multiplicative weights update method. We will also discuss some fundamental open questions, highlighting what algorithmic limitations need to be overcome for quantum computing to have an impact on the practice of optimization.
Chance constrained programs, which seek for a cost-optimal decision that satisfies a set of uncertain constraints with a pre-specified probability, constitute a popular and versatile method for decision-making under uncertainty. Since the true distribution governing the uncertain problem parameters is typically not known and thus has to be estimated from data, chance constrained programs often suffer from overfitting. In this talk, we study data-driven chance constrained programs that combat the issue of overfitting by hedging against all distributions sufficiently close to the empirical one, where proximity is measured by the Wasserstein distance. For individual chance constraints as well as joint chance constraints with right-hand side uncertainty, we provide exact mixed-integer conic programming reformulations. Using our reformulation, we show that two popular approximation schemes based on the conditional-value-at-risk and the Bonferroni inequality can perform poorly in practice. We conclude with numerical results.
Tutoriels
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.
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.
L'optimisation robuste (OR) est un des paradigmes disponibles 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. 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.
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.
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.
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. Retour d'expérience industrielle
Le challenge ROADEF
disponible en ligne ici : https://www.roadef.org/challenge/2020/en/sujet.php Manuel Ruiz (RTE) nous présente un problème de planification de maintenance du réseau électrique guidée par des coûts stochastiques liés aux risques évalués |
| Personnes connectées : 40 | Vie privée |
|
