On Complexity of Linear Bilevel Programming

摘要

In this paper, we study the Linear Bilevel Programming problem formulated as follows:rnmax_χ{as + Σ_(i=1)~k: x≥0},rnwhere y_i(x)'s are solutions to following k subordinate programs for i : 1≤i≤krns.t. max_(yi){c_ix + d_iy_i : A_ix + B_iy_i≤ C_i : y_i≤ 0}.rnSince this is known to be NP-hard [14], we are interested in studying the possibility of finding polynomial time algorithms for approximate solutions and/or for special cases. Unfortunately, we are able to show, there exists a constant ε > 0 such that it is NP-hard to find out an approximate solution which is at least (1 - ε) times optimum for this problem, even when there is only one subordinate program. On the other front, we discuss several general classes of this problem which can be solved in polynomial time.