The Burial of Coupling Constraints in Linear Bilevel Optimization.

Abstract: 

It has been common sense in (linear) bilevel optimization that problems with coupling constraints are more difficult to tackle than those without such constraints. While the modeling capabilities in terms of the feasible sets are indeed richer because coupling constraints allow to model disconnected feasible sets, complexity theory did not see any difference between problems with our without coupling constraints. In this talk, we show that there is no difference at all when one considers optimal solutions instead of just feasible points. For the case of optimistic bilevel problems, we proved this in 2024. The same result for pessimistic bilevel problems is from last week. In total, our results show that – on the level of optimal solutions – there is no difference between optimistic as well as pessimistic bilevel optimization with or without coupling constraints. As a “corollary” and rather surprisingly, all theoretical results and algorithms for pessimistic bilevel optimization without coupling constraints also apply to pessimistic bilevel optimization with coupling constraints.

Posted on Mar 10, 2025 in ACGO, Seminars