Some Ascpects of Bilevel Programming

Abstract

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. It has been applied to decentralized planning problems involving a decision process with a hierarchical structure. In this thesis we have discussed three problems in the field of bilevel optimization. In the first problem a bilevel linear/linear fractional programming problem has been discussed, where the objective function for the first level is linear, objective function for second level problem is linear fractional and the common constrained region is polyhedral. It has been discussed that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, by taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem. Second problem discussed in the thesis, consist of a linear fractional objective function at both the levels. It has been discussed that an optimal solution to this problem occurs at a boundary feasible extreme point. A Kth best algorithm has been proposed to solve this problems, further it has also been discussed this algorithm can also be extended to quasiconcave bilevel problems, provided that the first level objective function is explicitly quasimonotone. The last problem we have considered is a nonlinear bilevel programming problem, where the objective function of first level is a indefinite quadratic function and the lower level objective function is linear. By making use of duality theory, bilevel program is transformed into an equivalent single level programming problem, which can further be converted into a programming problem without constraints. By using genetic algorithm and optimal solution of this problem is obtained.