From Pessimistic Bilevel Optimization to Optimistic Bilevel Optimization

Most of the litereature on bilevel optimization focuses on the optimistic setting, where the lower-level problem is assumed to pick the solution in favor of the upper-level problem. However, there exists other notions such as pessimistic bilevel problems.

A pessimistic problem reads as follows:

(1)\[\begin{split}\begin{align} \min_{x} \quad & \max_{ y\in S(x) } \ F(x,y) \\ \text{s.t.} \quad & x\in X, \\ & S(x) \neq \emptyset, \end{align}\end{split}\]

with \(S(x)\) the solution set of

\[\begin{split}\begin{align} \min_{y} \quad & f(x,y) \\ \text{s.t.} \quad & g(x,y) \ge 0, \\ & y\in Y. \end{align}\end{split}\]

In this tutorial, we will show how a pessimistic bilevel problem can be automatically transformed into an optimistic bilevel problem. This transformation is due to [16].

Hint

Here, (1) does not have coupling constraints for simplicity. However, the transformation can be extended to bilevel problems with coupling constraints.

The Equivalent Optimistic Problem

In [16], the authors show that the pessimistic bilevel problem (1) is equivalent to the following optimistic bilevel problem:

(2)\[\begin{split}\begin{align} \min_{x,\bar y} \quad & F(x,y) \\ \text{s.t.} \quad & x\in X, \ \bar y\in Y, \\ & g(x,\bar y) \ge 0, \\ & y\in \tilde S(x, \bar y), \end{align}\end{split}\]

in which \(\tilde S(x, \bar y)\) is the solution set of

\[\begin{split}\begin{align} \min_y \quad & -F(x,y) \\ \text{s.t.} \quad & g(x,y) \ge 0, \\ & y\in Y, \\ & f(x,y) \le f(x, \bar y). \end{align}\end{split}\]

Note that (2) is an optimistic bilevel problem.

Implementation

Deriving the equivalent optimistic bilevel problem from a pessimistic bilevel problem can be done easily in idol.

To this end, let us assume that you have your bilevel problem already modeled in idol. In particular, let us consider that you have two variables:

1. high_point_relaxation which is a Model representing the high-point relaxation of your bilevel problem.

2. description which is a Bilevel:Description object representing the bilevel problem. If you do not know what this is or how to create it, please refer to the previous tutorial.

Then, you can derive the equivalent optimistic bilevel problem as follows:

auto [opt_model, opt_description] =
    Bilevel::PessimisticAsOptimistic::make_model(
                                        high_point_relaxation,
                                        description
                                );

Here, opt_model is the high-point relaxation of (2) and opt_description is the bilevel description of (2).

The rest of the code is the same as with any other solver. For instance, you can solve the optimistic bilevel problem with MibS as follows:

opt_model.use(Bilevel::MibS(opt_description));

opt_model.optimize();

std::cout << save_primal(opt_model) << std::endl;