The second level of the polynomial hierarchy contains a variety of optimization problems that can be naturally formulated with one existential and one universal quantifier. A typical example in robust optimization would ask whether there EXISTS some production plan that performs reasonably well under ALL possible price scenarios for electricity in the coming two years. Similarly, in bilevel optimization, a typical problem would ask whether there EXISTS a way of setting taxes so that ALL optimal behaviors of the citizens generate reasonable tax revenue.

Problems of this type are particularly difficult to solve from the point of view of mathematical optimization, requiring advanced tools based on decomposition algorithms, convex optimization, and combinatorial optimization. From the point of view of complexity theory, many of these problems are complete for the class Σ2p and are most likely not contained in the class NP. For that reason, the methodologies that have been developed for NP-complete problems over the last 50 years do not directly apply to robust and/or bilevel optimization problems.

While there has been some progress for purely convex problems, integer recourse (robust optimization) and integer follower problems (bilevel optimization) are still badly understood, yielding to the need to develop new techniques, tricks, insights, and algorithms to get a better grip on these problems.

The goal of this workshop is to bring together experts in combinatorial optimization, integer programming, and convex optimization, and we plan to work towards the following goals:

•  summarizing the status quo of robust optimization and bilevel optimization;
•  creating innovative connections between robust and bilevel optimization, helping the transfer of algorithms and reductions from one type of problems to the other;
•  identifying central research lines for computational and implementational aspects as well as in complexity theory.