Refine
Keywords
Mixed-Integer Optimization Techniques for Robust Bilevel Problems with Here-and-Now Followers
(2025)
In bilevel optimization, some of the variables of an optimization problem have to be an optimal solution to another nested optimization problem. This specific structure renders bilevel optimization a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications such as in critical infrastructure defense, transportation, or energy. Due to their nested structure, however, bilevel problems are also inherently hard to solve—both in theory and in practice. Further challenges arise if, e.g., bilevel problems under uncertainty are considered.
In this dissertation, we address different types of uncertainties in bilevel optimization using techniques from robust optimization. We study mixed-integer linear bilevel problems with lower-level objective uncertainty, which we tackle using the notion of Gamma-robustness. We present two exact branch-and-cut approaches to solve these Gamma-robust bilevel problems, along with cuts tailored to the important class of monotone interdiction problems. Given the overall hardness of the considered problems, we additionally propose heuristic approaches for mixed-integer, linear, and Gamma-robust bilevel problems. The latter rely on solving a linear number of deterministic bilevel problems so that no problem-specific tailoring is required. We assess the performance of both the exact and the heuristic approaches through extensive computational studies.
In addition, we study the problem of determining optimal tolls in a traffic network in which the network users hedge against uncertain travel costs in a robust way. The overall toll-setting problem can be seen as a single-leader multi-follower problem with multiple robustified followers. We model this setting as a mathematical problem with equilibrium constraints, for which we present a mixed-integer, nonlinear, and nonconvex reformulation that can be tackled using state-of-the-art general-purpose solvers. We further illustrate the impact of considering robustified followers on the toll-setting policies through a case study.
Finally, we highlight that the sources of uncertainty in bilevel optimization are much richer compared to single-level optimization. To this end, we study two aspects related to so-called decision uncertainty. First, we propose a strictly robust approach in which the follower hedges against erroneous observations of the leader's decision. Second, we consider an exemplary bilevel problem with a continuous but nonconvex lower level in which algorithmic necessities prevent the follower from making a globally optimal decision in an exact sense. The example illustrates that even very small deviations in the follower's decision may lead to arbitrarily large discrepancies between exact and computationally obtained bilevel solutions.