## Seminar: Selected Topics in Bilevel Optimization |

## Winter-Semester 2016/17 |

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

The kickoff, where every participant will give an overview (of at most five minutes) on their topic, will take place onTuesday, October 18, 2016 at 10:00 ct in room MA 212 at TU.

An additional mandatory winterschool on the topic of Bilevel Optimization is taking place on theMonday, November 07, 2016 at 10:00 ct in room MA144 at TU.

Finally, the main talks will be held on approximately two days in the week fromTBA

The two days will be fixed at the kickoff meeting. Dates and rooms are subject to change. Further dates will be appointed if neccessary.06 - 10 February 2017 at ZIB.

1. AF -Selected Topics in Bilevel Optimization

2. SF -

3. MA -

4. LE -

5. FK -

6. AW -

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.

Kai Hennig (hennig at zib.de)

Jakob Witzig (witzig at zib.de)

Prof. Dr. Thorsten Koch (koch at zib.de)