Seminar: Selected Topics in Bilevel Optimization
|
LV-Nr.: 3236 L 382
Contents
The seminar deals with selected topics in the area of Bilevel Optimization.
We want to discuss state-of-the-art solution approaches (especially for linear and mixed-integer bilevel programs),
interesting applications and their modelling, as well as some of the latest theoretical results.
What is Bilevel Optimization?
Since its first formulation by Stackelberg in his monograph on market economy in 1934 and the first mathematical model by Bracken and McGill in 1972 there has been a steady growth in investigations and applications of bilevel optimization. Formulated as a hierarchical game (the Stackelberg game), two decision makers act in this problem.
The so-called leader maximizes his objective function subject to conditions composed (in part) by optimal decisions of the so-called follower.
The selection of the leader influences the feasible set and the objective function of the follower's problem, whose reaction has strong impact
on the leader's payoff and feasibility of the leader's initial selection. [1]
An example for a Bilevel Optimization Problem, namely a Bilevel Linear Mixed-Integer Program (BLMIP), is depicted in the picture below [2].
Here, the leader tries to maximize his objective function "x+10y". Unfortunately, he can only decide about the assignment of the integer variable x.
Given his assignment of x, the follower chooses an assignment of the integer variable y maximizing his own objective "-y" while he must respect the given constraints.
Obviously, the decision made by the follower has a significant impact on the objective function value of the leader. Hence, it is necessary for the leader
to take the followers problem into account when deciding about the assignment of x.
For some more introductory details on the topic of Bilevel Optimization, including the meaning of the picture next to the example BLMIP, we recommend that you join
us at the initial meeting.
But as an appetizer we reveal the following "secret": In this example, the unique optimal solution is given by (x,y) = (2,2).
[1] Bilevel Programming Problems - Theory, Algorithms and Applications to Energy Networks, Dempe, Kalashnikov, Perez-Valdes, Kalashnykova
[2] https://www.semanticscholar.org/paper/A-Branch-and-cut-Algorithm-for-Integer-Bilevel-Denegre-Ralphs/8fde61e0f7eed35b62af13d6484beae660aac8b1
Timing
The initial meeting of the seminar (Vorbesprechung), where the participants register and are assigned papers, will take place on
Tuesday, October 18, 2016 at 10:00 ct
in room MA 212 at TU.
The kickoff, where every participant will give an overview (of at most five minutes) on their topic, will take place on
Monday, November 07, 2016 at 10:00 ct in room MA144 at TU.
An additional mandatory winterschool on the topic of Bilevel Optimization is taking place on the
TBA
Finally, the main talks will be held on approximately two days in the week from
06 - 10 February 2017 at ZIB.
The two days will be fixed at the kickoff meeting. Dates and rooms are subject to change. Further dates will be appointed if neccessary.
Kickoff Schedule
Selected Topics in Bilevel Optimization
1. AF - Pessimistic bilevel linear optimization (Dempe et al.) - The bilevel programming problem: reformulations, constraint qualifications and optimality conditions (Dempe and Zemkoho)
2. SF - Solving DAD Models for Infrastructure Defense (Alderson et al.) - Attacker-defender models and road network vulnerability (Bell et al.)
3. MA - Resolution method for mixed integer bi-level linear problems based on decomposition technique (Saharidis and Ierapetritou)
4. LE - Enhanced exact algorithms for discrete bilevel linear problems (Caramia and Mari)
5. FK - Bilevel Programming and the Separation Problem (Lodi et al.)
6. AW - Intersection cuts for bilevel optimization (Fischetti et al.)
Registration
Students interested in participating in the seminar are invited to come to the
initial meeting on the 18.10.2016 in room MA212. For additional informations please contact Prof. Dr. Thorsten Koch (koch at zib.de).
Seminar Requirements
Students interested in participating in the seminar are invited to come to the initial meeting taking place on the 18.10.2016 in room MA212.
Every participant is expected to attend all presentations of the seminar (including the kickoff). Additionally, there
will be a short Winter School of one or two days given by Prof. Dr. Ted Ralphs on the topic (The date is going to be fixed later),
which every participant must (and also should) attend.
All participants are free to choose their own lecture style. Blackboards and a projector will be available.
The lectures should last about 25-35 minutes (at most 45 including discussion). Every participant is also required to produce a
handout of about 5 pages summarizing the content of their own lecture.
Basic knowledge of Linear and/or Integer Programming, such as
taught in ADM I and II, is a prerequisite for this seminar.
Further Information
This seminar is an Advanced Course of the Berlin Mathematical School (BMS).
Contact
For additional information or if you have any further questions please contact:
Kai Hennig (hennig at zib.de)
Jakob Witzig (witzig at zib.de)
Prof. Dr. Thorsten Koch (koch at zib.de)
Last change: 25th October 2016
