A Modified Simplex Method for Solving Linear-Quadratic and Linear Fractional Bi-Level Programming Problem

Author's Name: Eghbal Hosseini and Isa Nakhai Kamalabadi
Subject Area: Science and Engineering
Subject Mathematics
Section Research Paper


The linear-quadratic bi-level programming, the penalty function method, simplex method, Karush-Kuhn–Tucker conditions.


The bi-level programming problem (BLP) is a suitable method for solving the real and complex problems in applicable areas such as management, economics, policies and planning and so on. There are several forms of the BLP as an NP-hard problem. The linear-quadratic bi-level programming (LQBP) and the linear-fractional bi-level programming (LFBP) are important forms of the BLP. In this paper, we attempt to develop two effective approaches, one based on modified simplex method and the other based on the genetic algorithm for solving the LQBP and LFBP. To obtain efficient upper bound and lower bound we employ the Karush -Kuhn -Tucker (KKT) conditions for transforming the LQBP into a single level problem. By using the proposed penalty functions, the single problem is transformed to an unconstraint problem and then it is solved by modified simplex method and genetic algorithm. The proposed approach achieves efficient and feasible solution and it is evaluated by comparing with references.

Download Full Paper