A Study of Bilevel Integer Quadratic Programming Problems

Abstract

Bilevel Programming Problem (BPP) is an intricate optimization problem which adhere to hierarchical structure and used for solving real life problems. In this dissertation, an algorithm for solving Quadratic Bilevel Integer Programming Problem is proposed. We have also reviewed an algorithm used for ranking the integer feasible solutions of Quadratic Integer Programming Problem. The thesis contains three major chapters and Bibliography in end.

First chapter consists of the introduction to Quadratic Programming Problem, Quadratic Integer Programming Problem, Bilevel Programming Problem and Quadratic Bilevel Integer Programming Problem. Some basic results and applications of these problems are discussed.

Second chapter elaborates the algorithm discussed by Renu and Puri [1]. The chapter delineates the algorithm used for ranking the integer feasible solutions of Quadratic Inte- ger Programming Problem. We have outlined the problem formulation and the theoretical

framework. Two numerical examples are discussed to explain the algorithm. One example is taken from Renu and Puri [1] and other is randomly generated in Matlab. We have also provided computational results for a large number of variables and constraints that were not provided in the paper.

In the third chapter an algorithm is proposed for finding an optimal solution of Quadratic Bilevel Integer Programming Problem (QBIPP). Also the algorithm works well for its special cases like integer linear bilevel programming problems. This algorithm can also be used to solve Linear Bilevel Integer Programming Problem (BLIPP). We have also created a code in Matlab to find optimal solution of this problem. We have shown the effectiveness of the proposed algorithm by solving QBIPP discussed in Nacera Maachou and Mustapha Moulaı [2], Ritu Narang and SR Arora [3] and BLIPP discussed in James T Moore and Jonathan F Bard [4]. One randomly generated QBIPP in Matlab is also solved. In addition, we have provided computational results for a large number of variables and constraints for both QBIPP and BLIPP.