Approximation Of A Two-tier Planning Theory And Algorithm

Bilevel programming problems have been extensively studied due to their po-tential applications in economics, management, military and many other fields. From the mathematical point of view, bilevel programming problems are compli-cated problems:They are NP-hard; for many of its reformulations as one-level opti-mization problems, the common constraint qualifications often can not be satisfied in feasible region. Focus in this thesis is on the items:approximation schemes for bilevel programming problems, heuristic algorithm and their applications in traffic network problems.Chapter 2 investigates the approximation of nonconcave bilevel programming problems. The main tool in the present literature to treat the bilevel program-ming problems is the methods of KKT conditions and value function. However, for the non-concave case, neither technique can be applied. Two concepts, e-set andε-error bounds, are proposed. By using certain e-uniform error bounds as theε-exact penalty, we give the single level problems equivalent to the approximate bilevel programming problems. Furthermore, under some conditions, we show that any cluster of the approximate sequence is the solution of the bilevel programming problems. Finally, we use a nonconcave bilevel programming problem to illustrate our results.In chapter 3, we consider the network optimization problems which have the following characteristics:control parameters vary continuously and network users behave according to Wardrop's first principle of traffic equilibrium. For the network problems, we have studies on the efficiency evaluation of a heuristic algorithm pre-viously proposed in the literature [41]. A heuristic algorithm is a technique designed to solve a problem that ignores whether the solution can be feasible or correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem. We introduce the notion, POA (Price of Anarchy), into the efficiency Evaluation in algorithm theory. By the generalized nonlinearity and steepness of mappings, we provide estimates on the efficiency of heuristic algorithm. In addition, examples are presented to illustrate the effectiveness of our results. Chapter 4 presents a rigorous mathematical analysis on the weak stability of mathematical programs with equilibrium constraints, in Hilbert space. We intro-duce the notions of approximating solution sequence and weak stability, then provide a sufficient condition for the weak stability of these programs. Based on the theo-retical results, we concern on the application of these bilevel programming models in transportation science:emission charging control. By introducing an auxiliary variational inequality, using Hoffman lemma and exact penalization method, we prove the existence of solutions for this application under mild condition. More-over, based on the discretization of the value of time, we obtain a finite program with equilibrium constraints. Such a program could provide us an approximating solution. Finally, we establish the weak convergence of the approximating solution sequence.