Modeling an Optimistic Bilevel Problem

In this tutorial, we will see how to model an optimistic bilevel problem in idol.

To follow this tutorial, you should be familiar with bilevel optimization and modeling optimization problems in idol. If this is not the case, we recommend you to read the tutorial on MIP modeling.

Problem Definition and Main Steps

We consider the optimistic bilevel problem

\[\begin{split}\begin{align} \min_{x, y} \ & -x + -10 y \\ \text{s.t.} \ & x \in \mathbb Z_+ \\ & y\in \begin{array}[t]{rl} \displaystyle \underset{y}{\text{arg min}} \ & y \\ \text{s.t.} \ & -25 x + 20 y \leq 30, \\ & x + 2 y \leq 10, \\ & 2 x - y \leq 15, \\ & 2 x + 10 y \geq 15, \\ & y \geq 0, \\ & y \in \mathbb Z_+. \end{array} \end{align}\end{split}\]

This is an ILP-ILP bilevel problem which is taken from [10] (Example 1).

To model this problem in idol, there are three main steps:

  1. Define the high-point relaxation (HPR) model, i.e., in our example,

    \[\begin{split}\begin{align} \min_{x, y} \ & -x + -10 y \\ \text{s.t.} \ & x \in \mathbb Z_+ \\ & -25 x + 20 y \leq 30, \\ & x + 2 y \leq 10, \\ & 2 x - y \leq 15, \\ & 2 x + 10 y \geq 15, \\ & y \geq 0, \\ & y \in \mathbb Z_+. \end{align}\end{split}\]

    This model defines all constraints and variables of the bilevel problem. The feasible region is classically called the shared-constraint set.

  2. Describe which variables and constraints are part of the lower-level problem.

  3. Define the lower-level objective function.

Modeling the High-Point Relaxation

The HPR can be modeled in the same way as a classical optimization problem. If you are not familiar with modeling optimization problems in idol, we recommend you to read the tutorial on MIP modeling.

Here is the code to model the HPR of the bilevel problem.

Env env;
Model high_point_relaxation(env);

auto x = high_point_relaxation.add_var(0, Inf, Integer, "x");
auto y = high_point_relaxation.add_var(0, Inf, Integer, "y");

high_point_relaxation.set_obj_expr(-x - 10 * y);
auto follower_c1 = high_point_relaxation.add_ctr(-25 * x + 20 * y <= 30);
auto follower_c2 = high_point_relaxation.add_ctr(x + 2 * y <= 10);
auto follower_c3 = high_point_relaxation.add_ctr(2 * x - y <= 15);
auto follower_c4 = high_point_relaxation.add_ctr(2 * x + 10 * y >= 15);

Describing the Lower-Level Problem

To describe the lower-level problem, we need to specify which variables and constraints are part of the lower-level problem. This done by creating an object of type Bilevel::LowerLevelDescription and calling the methods set_follower_var and set_follower_ctr.

Bilevel::LowerLevelDescription description(env);
description.set_follower_var(y);
description.set_follower_ctr(follower_c1);
description.set_follower_ctr(follower_c2);
description.set_follower_ctr(follower_c3);
description.set_follower_ctr(follower_c4);

Note that this does nothing more but to create two new Annotation<Var|Ctr> to indicate variables and constraints that are part of the lower-level problem. These annotations are used by the bilevel solver to identify the lower-level problem. In particular, all variables and constraints that are not annotated as follower variables or constraints are considered as leader variables and constraints and have an annotation which is equal to MasterId.

Also note that it is possible to create and use your own annotation. For instance, the following code is equivalent to the previous one.

Annotation<Var> follower_vars(env, MasterId, "follower_variables");
y.set(follower_vars, 0);

Annotation<Ctr> follower_ctrs(env, MasterId, "follower_constraints");
follower_c1.set(follower_ctrs, 0);
follower_c2.set(follower_ctrs, 0);
follower_c3.set(follower_ctrs, 0);
follower_c4.set(follower_ctrs, 0);


Bilevel::LowerLevelDescription description(follower_vars, follower_ctrs);

Defining the Lower-Level Objective Function

Finally, we need to define the lower-level objective function. This is done by calling the method set_follower_obj_expr on the object of type Bilevel::LowerLevelDescription. An Expr object is passed as argument to this method.

description.set_follower_obj_expr(y);

Complete Example

A complete example is available here.