Solving bi-level linear programmes
type: Item
instance of: scholarly article
title: Solving bi-level linear programmes
zbMATH Open document ID: 0856.90078
published in: Journal of Mathematical Analysis and Applications
publication date: 1996-08-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 894230
zbMATH Keywords: bi-level linear program
zbMATH Keywords: maxmin linear program
author: D. J. White
reviewed by: D. J. White
MaRDI profile type: Publication
full work available at URL: jmaa.1996.0202
OpenAlex ID: W2036796241
DOI: 10.1006/JMAA.1996.0202
description: scientific article; zbMATH DE number 894230