Solving an optimistic LP-LP bilevel problem with KKT reformulation

Problem Definition

This example is taken from [8] and is an LP-LP bilevel problem.

The problem is formulated as follows:

\[\begin{split}\begin{align} \min_{x, y} \quad & x + 6 y \\ \text{s.t.} \quad & -x + 5y \le 12.5, \\ & x \ge 0, \\ & y\in \begin{array}[t]{rl} \displaystyle \underset{y}{\text{arg min}} \quad & -y \\ \text{s.t.} \quad & 2 x - y \ge 0, \\ & -x - y \ge -6, \\ & -x + 6 y \ge -3, \\ & x + 3 y \ge 3. \end{array} \end{align}\end{split}\]

In this example, we will reformulate the bilevel problem as a single-level problem using the KKT conditions. The resulting problem will be solved by Gurobi as an NLP. Note that it is also possible to provide valid big-Ms to reformulate this problem as an MILP. Check out our tutorials to learn more.

Implementation