Research On Bilevel Programming

The use of mathematical programming in decision making is usually to solve problems with either a single overriding objective, or a variety of objectives dealt with by striving toward all of them simultaneously. All objectives are assumed to be those of single decision maker who has control over all decision variables. In practice, a hierarchical decision problem may has more than one decision makers, which have their own decision variables and objectives, and then the multilevel mathematical programming is a satisfying tool to solve these problems. Multilevel mathematical programming solves the problem of coordinating the decision making process in a decentralized system. In the definition multilevel mathematical programming, as one level of the hierarchy, a decision maker has his set of feasible solutions determined, in part, by the upper levels; conversely, the decision instruments he controls may allow him to influence the operations of the lower levels.A class of multilevel mathematical programming involves only two levels , and are called bilevel programming. In nature, a multilevel mathematical programming may be regarded as a composite of bilevel programming.A bilevel programming problem is presented in the form of static Stackelberg game. By assumption, play is sequential and uncooperative. However, the leader can influence the actions of the followers through a set of coordination variables while the follower's responses may partly determine the lead's payoff.This paper is devoted to analysing two classes of bilevel programming problems. Firstly, the linear bilevel programming, which all objective functions and constraints are linear, and the decision variables are continuous. Based on the linear bilevel programming's property, a extreme points algorithm algorithm is developed that finds global optima. Secondly, we examine a class of bilevel programmings where the leader tries to minimize a convex nonlinear objective function. The follower's objective function is a convex quadratic in a continuous decision space. All constrains are assumed to be linear. A branch and bound algorithm is developed that finds global optima.