JFLI Seminar on Combinatorial Optimization

Date: September 18th, 2015

Time: 14:00

Place: room 007, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo


Title: Optimization of dynamical systems, bilevel programming, observability on smart-grids

Speaker: Pierre-Louis Poirion (joint work with Sonia Toubaline, Claudia D’Ambrosio, Leo Liberti).

In the french « Sogrid » project about smart-grids, our aim is to place the minimum number of measurement devices on the links of a power-grid in order to « observe » to whole grid. After studying the complexity of the problem, we present a first natural but computationally unsatisfactory MILP model, which we reformulate into a bilevel program using a fixed point argument. We will then study a large class of dynamical systems depending on parameters which we want to optimize. We will show that under some dominance hypothesis, these problems can be reformulated into conic bilevel programs. We then present a new constraints and variables generation algorithm to solve the problem, and show that the observability problem can be solved by a simplified version of the algorithm. Finally we discuss some relations between the observability problem and the minimum rank of a graph and show that some bounds can be found to speed up the algorithm.

Bio: Pierre-Louis Poirion is now a postdoc at LIX – Ecole Polytechnique. He is interested in combinatorial optimization, bilevel and robust optimization, machine learning and operation research. He obtained his PhD at « Conservatoire des arts et metiers » at Paris in 2013 on robust optimization.


Title: The Johnson-Lindenstrauss Lemma in Linear and Integer Feasibility

Speaker: Leo Liberti (joint work with Vu Khac Ky, Pierre-Louis Poirion).

The Johnson-Lindenstrauss lemma allows dimension reduction on real vectors with low distortion on their pairwise Euclidean distances. This result is often used in algorithms such as $k$-means or $k$ nearest neighbours since they only use Euclidean distances, and has sometimes been used in optimization algorithms involving the minimization of Euclidean distances. In this paper we introduce a first attempt at using this lemma in the context of feasibility problems in linear and integer programming, which cannot be expressed only in function of Euclidean distances.

Bio: Leo Liberti obtained a PhD in optimization from Imperial College London in 2004. He became a professor at Ecole Polytechnique in 2006, and worked at IBM Research in 2012-2015 before joining CNRS and a Research Director. His other main interest is Mixed-Integer Nonlinear Programming.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *