The Properties Of And Algorithms For Bilevel Programming Problem

The theory issues and algorithms for bilevel programming problems(BPP) are studied. The properties of the feasible set and optimality conditions of BPP are discussed. Both the relation between BPP and DC programming problem(DCPP) and between BPP and biobjective programming problem(BBPP) are exploited. Several algorithms for BPP with linear lower-level multiobjective programming problem(BLLMPP) and bilevel integer programming problem(BIPP) are given and some incorrect conclusions of other author are pointed out. Details are as follows.As for BLLMPP, the properties and algorithms are discussed. First, it is proved that the feasible set of BLLMPP is connected and weakly quasiconvex, based on which, an extreme-point search algorithm is presented for BLLMPP with linear upper-level uniobjective programming problem. Then, an exact penalty function algorithm, on the basis of equivalent problem of lower-level programming problem and of the discussion of choosing initial value of and increasing in penalty factor, is given with its finite termination being proved. Furthermore, a branch and bound algorithm based on face search which comes from optimization over efficient set is described. Finally, numerical results are given and analyzed.The properties of two kinds of BPP and an algorithm for a BIPP are exploited. As for price control problem, the connectedness of the feasible set under the condition of admissible set being nonempty and bounded and its equivalence to a DCPP, are proved and with an example it is shown that the feasible set, generally, is not the union of faces of admissible set. The sufficient and necessary condition of the feasible set is given for quadratic BPP which is proved equivalent to a DCPP and with two counterexamples it is concluded that two conclusions of The Geometric Characteristic and Optimality Conditions of Quadratic BPP are not true. Regarding BIPP with all variants being integer, an algorithm with its advantages of irrelevance of the number of constraints and of achieving optimal solution is advanced.The discussion of the relation of bilevel linear programming problem(BLPP) and BBPP is also given. Under the assumption of admissible set being nonempty and bounded and that some optimal solution of BLPP is the efficient solution of the corresponding BBPP, it is proved that the optima which is efficient arrives at some extreme point of admissible set. Furthermore, two methods for finding an efficientsolution in different senses are presented and numerical examples are provided to compare the efficient solutions from different authors.