Programme > Exposés invités

Sur la résolution exacte des programmes quadratiques en nombres entiers et extensions

Sourour Elloumi, ENSTA ParisTech

Résumé : 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é.

 

Sourour Elloumi est Professeur de Recherche Opérationnelle à l'Unité de Mathématiques Appliquées de l'Ecole Nationale Supérieure des Techniques Avancées à Paris. Elle est également membre du Centre d'Etudes et de Recherches en Informatique et Communications du Cnam. Auparavant, elle était Maître de Conférences au Cnam puis à l'ENSIIE. Elle a effectué des séjours en tant que professeur invité à l'Université Libre de Bruxelles, à l'Université de Klagenfurt et à l'Université d'Aix-la-Chapelle. Ses travaux de recherche s'intéressent aux aspects méthodologiques de l'optimisation mathématique discrète, avec un focus sur l'optimisation quadratique. Elle s'intéresse également à différentes applications de la Recherche Opérationnelle, en particulier dans le domaine ferroviaire et celui des télécommunications.

 

A snapshot of quantum algorithms for optimization

Giacomo Nannicini, IBM T. J. Watson, New York

Abstract : 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.

Giacomo Nannicini is a Research Staff Member in the Theory of Quantum Computing and Information group at the IBM T. J. Watson Research Center. Before joining IBM, he was an assistant professor in the Engineering Systems and Design pillar at the Singapore University of Technology and Design. His main research interest is optimization broadly defined and its applications. Giacomo received several awards, including the 2016 COIN-OR Cup, the 2015 Robert Faure prize, the 2012 Glover-Klingman prize. His algorithms and software are used by one of the largest real-time traffic and mobility information groups in Europe and in IBM Watson Studio.

Data-Driven Chance Constrained Programs

Wolfram Wiesemann, Imperial College Business School, London

Abstract : 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.

Wolfram Wiesemann is Professor of Analytics and Operations as well as Fellow of the KPMG Centre for Advanced Business Analytics at Imperial College Business School, London. Before joining the faculty of Imperial College Business School in 2013, he was a post-doctoral researcher at Imperial College London (2010-2011) and an Imperial College Research Fellow (2011-2012). He was a visiting researcher at the Institute of Statistics and Mathematics at Vienna University of Economics and Business, Austria, in 2010, the Computer-Aided Systems Laboratory at Princeton University, USA, in 2011, and the Industrial Engineering and Operations Research Department at Columbia University, USA, in 2012. Wolfram’s research interests revolve around the methodological aspects of decision-making under uncertainty, as well as applications in logistics, operations management and energy.

 

---