Computational complexity of robust bilevel optimization problems

Abstract

Bilevel optimization is concerned with hierarchical optimization problems that involve two decision makers, a leader and a follower. Each player's decision influences the other player's optimization problem. Therefore, the leader has to anticipate the follower's reaction when taking the first decision, which can make the bilevel problem very hard to solve. In terms of computational complexity theory, combinatorial bilevel optimization problems are typically on the second level of the polynomial-time hierarchy.

In this thesis, we study three relatively easy and natural combinatorial bilevel optimization problems. The Bilevel Selection Problem and the Bilevel Continuous Knapsack Problem can be solved in polynomial time and the Bilevel Minimum Spanning Tree Problem is NP-equivalent. In all of them, the leader and the follower each control a subset of some set of items, and they build a feasible solution of the underlying single-level problem together, while optimizing different objective functions.

In case of the Bilevel Minimum Spanning Tree Problem, we also investigate the approximability and the special case where the number of follower's edges is small, and we characterize the complexity of problem variants involving bottleneck objective functions.

Besides the complexity of bilevel optimization problems, we also study the additional complexity that uncertainty introduces in bilevel problems. In our setting of robust bilevel optimization, we assume that the leader does not have full information about the follower's objective function and optimizes for the worst case among the possible follower's reactions. We consider several types of uncertainty sets that are typically used in robust optimization, such as discrete uncertainty, interval uncertainty, and discrete uncorrelated uncertainty, and study the effect that the robustness has on the underlying bilevel problem, in terms of its computational complexity.

We present complexity results for a class of robust linear bilevel problems with discrete leader's and continuous follower's decisions and we thoroughly study robust versions of the polynomial-time solvable Bilevel Selection Problem and Bilevel Continuous Knapsack Problem. Some of them are still solvable in polynomial time, while others are NP-hard. These results reveal several differences between robust bilevel optimization and robust single-level optimization. For example, in the former case, interval uncertainty is not trivial and an uncertainty set can usually not be replaced by its convex hull without changing the problem.