Date:

Vendredi, 7 octobre, 2016

**Le VENDREDI 7 OCTOBRE 2016**

Au laboratoire LIP6 de l’Université Pierre et Marie Curie - Paris 6

4 place Jussieu Paris 6 (métro Jussieu)

**Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105**

Sur le thème

Ce séminaire est libre d'accès mais merci de vous** inscrire **en utilisant l'onglet situé en-haut de page pour faciliter l'organisation.

Cliquer ici pour voir la liste des inscrits

Programme de la journée:

**9h30-10h00 Accueil "café - viennoiserie"**

**10h00-10h50; a coffee break of 20mn; and the talk continue 11h10-12h00**

**Martine Labbé**

Computer Science Department, Université Libre de Bruxelles

**Bilevel programming: Stackelberg games and pricing problems.**

A bilevel optimization problem consists in an optimization problem in which some of the constraints specify that a subset of variables must be an optimal solution to another optimization problem. This paradigm is particularly appropriate to model competition between agents, a leader and a follower, acting sequentially.

These lectures will be devoted to two important bilevel optimization problems.

In the first one, called the network pricing problem, tolls must be determined on a specified subset of arcs of a multicommodity transportation network. The leader or first level corresponds to the profit maximizing owner of the subset of arcs and the follower to users traveling at minimum cost between nodes of the network.

The second problem, called the Stackelberg bimatrix game, involve a party with the capacity of committing to a given action or strategy, referred to as the leader, and a party responding to the leader's action, called the follower. The objective of the game is for the leader to commit to a reward-maximizing strategy anticipating that the follower will best respond.

We will review these classes of hierarchical problems from both theoretical and algorithmic points of view and then focus on some special cases. Among others, we present complexity results, identify some polynomial cases and propose and compare mixed integer linear formulations.

**12h00-14h00 Repas**

**14h00 - 15h00**

**Ivana Ljubic**

ESSEC Business School of Paris

Joint work with M. Fischetti, M. Monaci, M. Sinnl

**A new general-purpose algorithm for mixed-integer bilevel linear programs**

In many important practical contexts, including pricing mechanisms in the energy sector, airline and telecommunication industry or transportation networks, bilevel optimization problems give rise to very challenging optimization models.

In this talk, a new general purpose branch-and-cut framework for the exact solution of mixed-integer bilevel linear programs (MIBLP) is presented. We first propose necessary extensions needed to turn a standard branch-and-bound MILP solver into an exact MIBLP solver. Contrarily to previous approaches, in our exact framework both leader and follower problems can be of mixed-integer type---provided that the leader variables influencing follower's decisions are integer and bounded. We introduce new classes of linear inequalities to be embedded in this branch-and-cut framework, some of which are intersection cuts based on feasible-free convex sets. We also propose an effective bilevel-specific preprocessing procedure.

An in-depth computational study is presented, where we evaluate the performance of various solution methods on a common testbed of more than 800 instances from the literature---this is by far the most extensive computational analysis ever performed for exact MIBLP solvers. Our new algorithm consistently outperforms (often by a large margin) all alternative state-of-the-art methods from the literature, including problem-tailored methods. In particular, we can now solve to proven optimality more than 300 previously unsolved instances from literature.

**15h00 - 15h30**

**Pierre-Louis Poirion**

joint work with Jean-François Baffier and Vorapong Suppakitpaisarn

**Bilevel Model for Adaptive Network Flow Problem**

We propose to solve the adaptive network flow problem via a bilevel optimization framework. In this problem, we aim to find a flow that is most robust against an optimal *k* edges attack. There is an exact algorithm proposed to solve

the problem in a special class of input graphs. However, for some input graphs that are not in that class, a flow obtained from the algorithms sometimes much less robust than the optimal one. That motivates us to find an efficient exact algorithm

based on bilevel optimization framework for the problem in this paper.

**15h30 - 15h50 Pause**

**15h50 - 16h50**

**Léo Liberti**

CNRS & Ecole Polytechnique

Joint work with C. D'Ambrosio, P.L. Poirion and S. Toubaline

**Controlling fixed points**

Simulation optimization consists of optimally deciding the parameters of a discrete dynamical system (DDS) so it achieves an output with given properties. This problem is universal, since the Halting problem can be reduced to it. The DDS dynamics may be unpredictable, since they can approximate a chaotic dynamical system. They are also unlearnable, since a DDS can be encode a pseudorandom generator, making this problem arguably the most difficult I have ever seen. And yet this is the problem that most practitioners in industry ask me to solve, usually because they want to optimally set the parameters of a piece of software that cannot be "opened", either because the source is not available, or because it is unwieldy, or both. For a long time, my first reaction has been to throw my arms up in despair. Recently, however, I have been looking at special types of DDS, namely those having a fixed point which can be described independently of the dynamics. I will describe these as bilevel mixed-integer programs (MIP), illustrate their generality by showcasing some wildly different applications, and discuss a cutting plane algorithm for a fairly general class of bilevel MIPs which, notwithstanding its worst-case exponential behaviour, seems to work surprisingly well.