Solving bi-level linear programmes (Q1915600)

This paper considers the following bi-level linear programme (BLP): maximise \([F(x, y)= ax+ by]\), where \(y\in \arg\max[f(x, y)= cx+ dy]\), \(Ax+ By\leq e\), and \(a, c\in R^{n_1}\); \(b, d\in R^{n_2}\); \(A\in R^{m\times n_1}\); \(B\in R^{m\times n_2}\); \(e\in R^m\). The problem BLP is transformed into an equivalent maxmin linear programme (MMLP(\(K\))): \(\underset {z\in Z_v, u\in R^{n_1}}{\text{maxmin}} [P(K; z, u)= ax+ by+ K(dy- du)]\), subject to \(Ax+ By\leq e\), \(Ax+ Bu\leq e\), where \(z= (x, y)\) and \(Z_v\) is the feasible set of the \(z\) region. Let \(S(x)= \{y\in R^{n_2}: z\in Z\}\), \(x\in X\). The following theorem is established. Theorem. (i) There exists \(K^*\in R_+\) such that if \(K\geq K^*\) and \((z, u)\) solves problem MMLP(\(K\)) then \(z\) solves problem BLP; (ii) If \(z\) solves problem BLP, then, for the \(\{K\}\) of part (i), \((z, u)\) solves problem MMLP(\(K\)) for some \(u\in S(x)\); (iii) If \((z, u)\) solves problem MMLP(\(K\)), then \(z\) solves problem BLP. Some comments are given concerning the solution process.