Bilevel optimization with linear objectives and constraints

Question

I'm looking at the following bilevel optimization problem, where $x \in R^n$ denotes the upper-level variables and $y \in \mathbb{R}^m$ denotes the lower-level variables. The vectors $a,b,c$ and $d$ are strictly positive integral vectors of appropriate lengths.

$$ \begin{align} \max_{x \in \mathbb{R}^n} &~a \cdot x + (b,-c) \cdot y \\ ~s.t.~ &~y \in \text{argmin}_{y \in \mathbb{R}^m} \{(b,c) \cdot y \mid y \geq 0, x_i + y_j \leq d_i \forall i \in \{1,\ldots, n\}, j \in \{1, \ldots, m\} \}. \end{align} $$ I read on this Wikipedia page on bilevel optimization that one approach is to replace the lower optimisation problem with its KKT conditions. But as the lower optimisation problem is a linear program, I am stuck.

The problem looks fairly benign. Any ideas that might allow me to solve it in polynomial time?

Answer 1

For LP, the KKT conditions are primal feasibility, dual feasibility, and complementary slackness: \begin{align} x_i + y_j &\le d_i &&\text{for all $i,j$}\\ y_j &\ge 0 &&\text{for all $j$}\\ \sum_i z_{ij} &\le (b,c)_j &&\text{for all $j$} \\ z_{ij} &\le 0 &&\text{for all $i,j$} \\ \left(\sum_i z_{ij} - (b,c)_j\right) y_j &= 0 &&\text{for all $j$} \\ (x_i + y_j - d_i)z_{ij} &= 0 &&\text{for all $i,j$} \end{align} Now maximize $a\cdot x+(b,-c)\cdot y$ subject to these constraints.