SPOC15 "Combinatorial Bi-level optimization"
Date:
Friday, 7 October, 2016
15ème séminaire du groupe POC
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
"Combinatorial Bi-level optimization"
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.