Abstract
Linear bilevel programming (BLP) problem is a special case of multilevel programming problem, which is a mathematical programming model for decentralized decision problems. In a linear BLP problem, the higher and the lower levels objective functions are both linear functions and the constraints region is a convex set, however, the rational reaction set (or, the feasible set) is generally nonconvex. Hence the linear BLP problem is mathematically classified as a nonlinear optimization problem.In this dissertation, based on primal and primal-dual affine scaling algorithms, we develop interior point algorithms for solving linear BLP problems. We test the accuracy and efficiency of the proposed algorithms by solving randomly generated problems. The computational results show that the interior point method is suitable for solving relatively larger scale linear BLP problems.On the other hand, after modification, the proposed interior point algorithm also provides an effective and accurate approach to solve linear optimization over the efficient set (OES) problems. The computational results also show that the modified algorithm can solve relatively larger scale linear OES problems.