Recent algorithmic advances in bilevel optimization
Bilevel optimization is a wonderful area of mathematical optimization. There are at least two reasons. First, bilevel optimization problems today serve as a powerful modeling tool to formalize hierarchical decision making processes. This leads to an enormous amount of applications ranging from energy markets or machine learning over pricing problems in revenue management to critical infrastructure defense or anti-poaching problems. Second, bilevel problems are inherently nonconvex and thus hard to solve both in theory and practice. What might sound as a disadvantage of the field at a first glance, in the end lead to a growing number of researchers that study theoretical well-posedness issues, equivalent reformulations, or effective solution methods.
The increasing number of applications also lead to more and more challenging classes of bilevel problems that emerged over the last years and decades. Without any specific chronological order, these challenges are given by mixed-integer aspects, continuous but nonlinear nonconvexities, or even black-box constraints that all particularly increase the hardness of the overall bilevel problem if they are part of the lower level.
In this talk, we give an overview of the developments of the area with a focus both on the above mentioned challenges as well on the algorithmic advancements in the corresponding fields. In particular, we focus on mixed-integer and continuous but nonlinear aspects. For the latter, we discuss those situations in which the lower-level problem can only be solved to approximate feasibility. We motivate this setting by a chance-constrained bilevel model of the EU gas market and discuss the obstacles and pitfalls of inexact lower-level solutions – issues for which the speaker will mostly pose future research questions for the audience than presenting own and already existing results.