GENETIC ALGORITHM FOR SOLVING CONVEX QUADRATIC BILEVEL PROGRAMMING PROBLEMS

Abstract

Bilevel programming problems (BPPs) are a class of challenging optimization problems, which contain two levels of optimization tasks, the upper level and the lower level. This project developed to solve BPP using genetic algorithms (GAs) especially for the problems with convex quadratic objective functions and linear constraints which is convex quadratic bilevel programming problems (CQBPPs). Since GAs work with a population of points, it seems natural to use GAs in bilevel optimization problems to capture a number of solutions. Using the KarushKuhn-Tucker (KKT) optimality conditions of the lower level optimization problem, the original bilevel programming problem formulation can be converted into a single level optimization problem with the complementarity constraints. Customized genetic algorithms have been demonstrated to be particularly effective to determine good approximate solutions for the transformed single level problem. Finally, the solutions of the problems of examples are obtained using MATLAB mathematical software. The algorithm has repeatedly modified a population of individual solutions by applying different runs of the same GA code to build confidence in the solution. In the computational experiment, four problems are solved, and the results show that the proposed algorithm achieves an efficient and feasible solution in an appropriate time which has been evaluated by comparing to references.