=============================================================================

Arbeitsbericht Nr. 12, Februar 1996, Universitaet Leipzig, Wirtschaftswissenschaftliche Fakultaet, Institut für Informatik

Bilevel programming problems are hierarchical optimization problems in which the feasible set is determined by the set of optimal solutions of a second, parametric optimization problem. In this paper we consider problems where this second problem is a discrete one. We start with addressing the problem of the existence of optimal solutions. Then, an algorithm is proposed solving these problems. This method uses a cutting plane approach for approximating the feasible set of the discrete lower level problem. The paper is closed with some remarks concerning the computation of bounds for the optimal function value of the discrete bilevel programming problem.

Bilevel programming problems are of growing interest both from a theoretical and a practical points of view. They can be interpreted as certain non-cooperative non-zero sum hierarchical games. Here, one player, the so-called follower, has to solve a parametric optimization problem when computing his decision. If this decision is not uniquely determined, then the other player, the so-called leader, is not able to predict the real outcome of the game since his objective depends on his own choice as well as on the follower's response. In this paper, we treat this case and propose a new idea for generating a satisfactory decision for the leader. In short, we propose the leader to take on an optimistic position combined with a following perturbation of the decision thus obtained. Practicability of a major part of this approach is also shown.

Let $x^0$ be a locally optimal solution of a smooth parametric nonlinear optimization problem $\min\{f(x,y): g(x,y)\leq 0,\ h(x,y)=0\}$ for a fixed value $y=y^0$. If the strong sufficient optimality condition of second order together with the Mangasarian-Fromowitz and the constant rank constraint qualifications are satisfied, then $x^0$ is strongly stable in the sense of Kojima and the corresponding function of locally optimal solutions of perturbed problems is locally Lipschitz continuous. In the paper we give one tool for computing its generalized Jacobian. We also show that this function is quasidifferentiable in the sense of Dem'yanov and Rubinov and describe one quasidifferential. In the last part of the paper a method is developed for reducing the quasidifferential which is especially useful when both the super- and the subdifferential are spanned by finitely many elements as in our case.

In the paper a method for solving bilevel programming problems by means of applying the bundle idea is proposed. Two examples show how bilevel programming can be used for finding best environmental policies in hierarchical economical systems.

Preprint 97-06, Fakultät für Mathematik und Informatik, Technische Universität Bergakademie Freiberg

In this paper we consider bilevel programming problems in which the lower level problem is not assumed to have unique optimal solutions for all values of the parameter. Using common approaches to treat such problems, a generally discontinuous function is to be minimized. This leads to the definition of a new class of functions, so-called generalized $PC^1$-functions which are composed by a finite number of continuously differentiable functions. We investigate them using the radial-directional derivative and a radial subdifferential and give criteria for optimality for minimizing such a function. These results are then applied to linear bilevel programming problems.

In the paper, the question is investigated if a bundle algorithm can be used to compute approximate solutions for bilevel programming problems where the lower level optimal solution is in general not uniquely determined. To give a positive answer to this question, an appropriate regularization approach is used in the lower level. By use of an additional assumption, it is even possible to show convergence of the algorithm to a stationary solution of the bilevel problem.

TU Bergakademie Freiberg, Fakultät für Mathematik und Informatik, D-09596 Freiberg, Germany

Preprint 97-10, Fakultät für Mathematik und Informatik, Technische Universitaet Bergakademie Freiberg

If a strong sufficient optimality condition of second order together with the Mangasarian-Fromowitz and the constant rank constraint qualifications are satisfied for a parametric optimization problem, then a local optimal solution is strongly stable in the sense of Kojima and the corresponding optimal solution function is locally Lipschitz continuous. In the article the possibilities for the computation of subgradients of this function are discussed. We will give formulae for the guaranteed computation of the entire subdifferential, provided that an additional assumption is satisfied. An example will show the necessity of this assumption. Moreover, this assumption is difficult to be verified. Without it, a subgradient can be computed with non-polynomial complexity in the worst case. A last approach yields a subgradient with probability one in polynomial time.

J.F. Bard, Graduate Program in Operations Research, University of Texas, Austin, U.S.A.

Preprint 99-4 TU Bergakademie Freiberg, Fekultät für Mathematik und Informatik

The bilevel programming problem (BLPP) is equivalent to a two-person Stackelberg game in which the leader and follower pursue individual objectives. Play is sequential and the choices of one affect the choices and attainable payoffs of the other. The purpose of this paper is to investigate an extension of the linear BLPP where both players' objective functions are bilinear. To overcome certain discontinuities in the master problem, a regularized term is added to the follower's objective function. Using ideas from parametric programming, the directional derivatives of the regularized follower's solution function are computed along with its generalized Jacobian. This allows us to develop a bundle trust region algorithm. Theoretical results related to the existence of solutions are presented as well as a convergence analysis of the proposed methodology.

S. Dempe, Freiberg University of Mining and Technology

Preprint TU Bergakademie Freiberg Nr. 2000-03, Fakultät für Mathematik und Informatik (preprint of a paper published in European Journal of Operational Research, 136(2002), 46-56. copyright: Elsevier Science B.V.)

We consider the problem of optimally allocating the resources to competing activities where the amounts of the resources are not previosly given but are also to be determined subject to certain linear constraints. The objective is to find such activity levels such that their weighted deviation from a prespecified target is as small as possible. We suggest a primal decomposition approach for the problem and derive an explicit formula for the piecewise affine-linear convex objective function of the upper level problem. The lower level problem is a parametric optimization problem with a bottleneck objective function. If the constraints on the amounts of the resources are all of knapsack type or if there is only one such constraint, then the upper level problem is equivalent to the lower level problem with fixed right-hand sides. In the general case, the problem can efficiently be solved by means of the level method.

K. Richter, Technical University Chemnitz

Preprint TU Bergakademie Freiberg Nr. 2000-05, Fakultät für Mathematik und Informatik

A special class of bilevel programming problems with discrete parametric lower level problems is considered. First, necessary and sufficient conditions for the existence of optimal solutions are given. Then, a pseudopolynomial exact and a polynomial approximate algorithms for solving the bilevel problem in the weak and in the strong senses are proposed.

Central European Journal of Operations Research 8(2000)2, pp. 93--107 (Copyright: Springer Verlag)

A special class of bilevel programming problems with discrete parametric lower level problems is considered. First, necessary and sufficient conditions for the existence of optimal solutions are given. Then, a pseudopolynomial exact and a polynomial approximate algorithms for solving the bilevel problem are proposed.

Preprint TU Bergakademie Freiberg Nr. 2003-01, Fakultät für Mathematik und Informatik

In this bibliography main directions of research as well as main fields of applications of bilevel programming problems and mathematical programs with equilibrium constraints are summarized. Focus is also on the difficulties arising from nonuniqueness of lower-level optimal solutions and on optimality conditions. The reference list in Bibtex format is in the file bibliography_references.bib . For the abbreviations of journals see ABK1.bib

Preprint TU Bergakademie Freiberg Nr. 2003-10, Fakultät für Mathematik und Informatik, 2003

In this paper, we present a mathematical framework for the problem of minimizing the cash-out penalties of a natural gas shipper. The problem is modeled as a mixed-integer bilevel programming problem having one Boolean variable in the lower level problem. Such problems are difficult to solve. To obtain a more tractable problem we move the Boolean variable from the lower to the upper level problem. The implications of this change of the problem are investigated thoroughly. The resulting lower level problem is a generalized transportation problem. The formulation of conditions guaranteeing the existence of an optimal solution for this problem is also in the scope of this paper. The corresponding results are then used to find a bound on the optimal function value of our initial problem.

We investigate a special mixed-discrete bilevel programming problem resulting from the task to compute cash-out penalties due to the supply of incorrect amounts of natural gas through large gas networks. For easier solution we move the discreteness demand from the lower to the upper levels. This clearly changes the problem and it is our aim to investigate the relations between both problems. After the move, a parametric generalized transportation problem arises in the lower level for which the formulation of conditions for the existence of an optimal solution is our first task. In the second part of the paper, requirements guaranteeing that an optimal solution of the original problem is obtained by solving the modified one as well as bounds for the optimal value of the original problem are derived.

Preprint TU Bergakademie Freiberg Nr. 2003-11, Fakultät für Mathematik und Informatik, 2003

Bilevel programming problems are hierarchical optimization problems where an objective function is to be minimized over the graph of the solution set mapping of a second parametric optimization problem. It is the aim of the paper to give a survey for this living research area indicating main recent approaches to solve such problems and to describe optimality conditions as well as to touch main particularities of this problem class.

Preprint TU Bergakademie Freiberg Nr. 2003-09, Fakultät für Mathematik und Informatik, 2003

Linear programming problems with fuzzy coefficients in the objective function are considered. Emphasis is on the dependence of the optimal solution from linear perturbations of the membership functions of the objective function coefficients as well as on the computation of a robust solution of the fuzzy linear problem if the membership functions are not surely known.

Preprint TU Bergakademie Freiberg Nr. 2005-1, Fakultät für Mathematik und Informatik, 2005

In this paper a special step control problem is considered. The formulation of the problem uses a parameter to control the switching point. By using Taylor's increment methods first and second order optimality conditions (in the sense of Pontryagin's maximum principle) will be derived.

In: Recent Advances in Optimization. Proceedings of the 12th French-German-Spanish Conference on Optimization held in Avignon, September 20-24, 2004, Edited by A. Seeger. Lectures Notes in Economics and Mathematical Systems, Springer-Verlag

Abstract: Let $\,\varPsi(b,c)\,$ be the solution set mapping of a linear parametric optimization problem with parameters $\,b\,$ in the right hand side and $\,c\,$ in the objective function. Then, given a point $\,x^0\,$ we search for parameter values $\,\overline{b}\,$ and $\,\overline{c}\,$ as well as for an optimal solution $\,\overline{x}\in \varPsi(\overline{b},\overline{c})\,$ such that $\,\|\overline{x}-x^0\|\,$ is minimal. This problem is formulated as a bilevel programming problem. Focus in the paper is on optimality conditions for this problem. We show that, under mild assumptions, these conditions can be verified in polynomial time.

Preprint TU Bergakademie Freiberg, Nr. 2005-5, Fakultät für Mathematik und Informatik, 2005

Focus in the paper is on the definition of linear bilevel programming problems, the existence of optimal solutions and necessary as well as sufficient optimality conditions. In the papers \cite{ShiZhLu05} and \cite{ShZhLu05} the authors claim to suggest a refined definition of linear bilevel programming problems and related optimality conditions. Mainly their attempt reduces to shifting upper level constraints involving both the upper and the lower level variables into the lower level. We investigate such a shift in more details and show that it is not allowed in general. We show that an optimal solution of the bilevel programming problem exists under the conditions in [10] if we add the assumption that the inducible region is not empty. The necessary optimality condition reduces to check optimality in one linear programming problem. Optimality of one feasible point for a certain number of linear programs implies optimality for the bilevel problem.

Preprint TU Bergakademie Freiberg, Nr. 2005-4, Fakultät für Mathematik und Informatik, 2005

Abstract: In this work, we use a notion of convexificator together with the support function to establish necessary optimality conditions for set valued bilevel optimization problems. Fortunately, the Lipschitz property of a set-valued mapping is conserved for its support function. An intermediate set-valued optimization problem is introduced to help us in our investigation.

Preprint TU Bergakademie Freiberg, Nr. 2005-6, Fakultät für Mathematik und Informatik, 2005

Ausgehend von einem Strassennetz, einer gegebenen OD-Matrix und Kostenfunktionen wird eine Zwei-Ebenen-Optimierungsaufgabe zur Berechnung einer optimalen Mautgebuehr entwickelt. Was hierbei der Begriff optimal bezueglich der Maut bedeutet, wird allgemein durch eine Funktion F(x,c) ausgedrueckt. Als wesentlich erweist sich die einfache Beschreibung und Berechnung moeglichst realitaetsnaher Verkehrsfluesse. Daher werden systemoptimale Fluesse sowie Gleichgewichtsfluesse sowohl im unkapazitierten als auch im kapazitierten Netzwerk eingefuehrt.

Working Paper, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, September 2007

In this paper we formulate the fuzzy bilevel programming problem and describe one possible approach for formulating a crisp optimization problem being attached to it. Due to the nature of fuzzy bilevel programming this is a crisp bilevel programming problem. We compare our approach with one using multicriterial optimization and show, that both approaches are basically different. The use of multicriterial optimization rests on reformulating the original problem into a multicriterial fuzzy optimization problem and thus in deleting the hierarchical structure of the problem.

Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2008-05

() Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2009-01

In this paper, we study the application of a class of direct search methods to bilevel programming with convex lower level problems with strongly stable optimal solutions. In those methods, directions of descent in each iterations are selected within a finite set of directions. To guarantee the existence of such a finite set, we investigate the relation between the aperture of a descent cone at a non stationary point and the vector density of a finite set of directions. It is shown that the direct search method converges to a Clarke stationary point of the bilevel programming problem.

() Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2009-02

In this paper, we investigate the application of feasible direction method for an optimistic nonlinear bilevel programming problem. The convex lower level problem of an optimistic nonlinear bilevel programming problem is replaced by relaxed KKT conditions. The feasible direction method developed by Topkis and Veinott is applied to the auxiliary problem to get a Bouligand stationary point for an optimistic bilevel programming problem.

Bilevel programming problems are often reformulated using the Karush-Kuhn-Tucker conditions for the lower level problem resulting in a mathematical program with complementarity constraints (MPCC). Clearly, both problems are closely related. But the answer to the question posed is ``No" even in the case when the lower level programming problem is a parametric convex optimization problem. This is not obvious and concerns local optimal solutions. We show that global optimal solutions of the MPCC correspond to global optimal solutions of the bilevel problem provided the lower-level problem satisfies the Slater's constraint qualification. We also show by examples that this correspondence can fail if the Slater's constraint qualification fails to hold at lower-level. When we consider the local solutions, the relationship between the bilevel problem and its corresponding MPCC is more complicated. We also demonstrate the issues relating to a local minimum through examples.

We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem in transportation, and show how KKT type optimality conditions can be obtained under the partial calmness, using the differential theory of Mordukhovich.

Abstract: In the present paper recent concepts of the solution of the fuzzy optimization problem based on the level-cut, the interval arithmetic and the Pareto set notions were generalized. Using basic methods of convex multiobjective optimization necessary and sufficient conditions were derived.

Abstract: In the present paper recent concepts of the fuzzy solution of the fuzzy optimization problem based on the level-cut and the set of Pareto optimal solutions of a multiobjective optimization problem were applied to the fuzzy linear optimization problem. The purpose consists in describing a membership function of a fuzzy solution of the fuzzy optimization problem.

Abstract: This paper is mainly concerned with the classical KKT reformulation and the primal KKT reformulation (also known as an optimization problem with generalized equation constraint (OPEC)) of the optimistic bilevel optimization problem. A generalization of the MFCQ to an optimization problem with operator constraint is applied to each of these reformulations; hence leading to new constraint qualifications (CQs) and optimality conditions for the bilevel optimization problem. Strikingly, we also obtained that the optimality conditions of an OPEC coincide with those of a certain mathematical program with complementarity constraints (MPCC), which is a new result. In this paper, a concept of partial calmness known for the optimal value reformulation is also introduced for the primal KKT reformulation and as expected, it is shown to be strictly implied by the basic CQ.

In 1997, Macal and Hurter have found that adding a constraint to the lower level problem, which is not active at the computed global optimal solution, can destroy global optimality. In this paper this property is reconsidered and it is shown that this solution remains locally optimal under inner semicontinuity of the original solution set mapping. In the second part of the paper we prove that adding a variable in the linear lower level problem can also destroy global optimality. But here the solution remains locally optimal, provided the optimal solution in the lower level was dual non-degenerated.

We consider the bilevel programming problem with a special lower level. As a reformulation, we use the optimal value approach which will be the basis for an outer approximation. We establish an algorithm that sequentially improves the approximation in order to solve the bilevel programming problem. Convergence results for both local and global optima are presented.

The paper is concerned with the optimistic formulation of a bilevel optimization problem with multiobjective lower-level problem. Considering the scalarization approach for the multiobjective program, we transform our problem into a scalar-objective optimization problem with inequality constraints by means of the well-known optimal value reformulation. Completely detailed first-order necessary optimality conditions are then derived in the smooth and nonsmooth settings while using the generalized differentiation calculus of Mordukhovich. Our approach is different from the one previously used in the literature and the conditions obtained are new and furthermore, they reduce to those of a usual bilevel program if the lower-level objective function becomes single-valued.

This paper contributes to a deeper understanding of the link between a now conventional framework in hierarchical optimization spread under the name of the optimistic bilevel problem and its initial more diffcult formulation that we call here the original optimistic bilevel optimization problem. It follows from this research that, although the process of deriving necessary optimality conditions for the latter problem is more involved, the conditions themselves do not -- to a large extent -- differ from those known for the conventional problem. It has been already well recognized in the literature that for optimality conditions of the usual optimistic bilevel program appropriate coderivative constructions for the set-valued solution map of the lower-level problem could be used, while it is shown in this paper that for the original optimistic formulation we have to go a step further to require and justify a certain Lipschitz-like property of this map. This occurs to be related to the local Lipschitz continuity of the optimal value function of an optimization problem constrained by solutions to another optimization problem; this function is labeled here as the two- level value function. More generally, we conduct a detailed sensitivity analysis for value functions of mathematical programs with extended complementarity constraints. The results obtained in this vein are applied to the two-level value function and then to the original optimistic formulation of the bilevel optimization problem, for which we derive verifiable stationarity conditions of various types entirely in terms of the initial data.

This paper is devoted to the so-called pessimistic version of bilevel programming programs. Minimization problems of this type are challenging to handle partly because the corresponding value functions are often merely upper (while not lower) semicontinuous. Employing advanced tools of variational analysis and generalized differentiation, we provide rather general frameworks ensuring the Lipschitz continuity of the corresponding value functions. Several types of lower subdifferential necessary optimality conditions are then derived by using the lower-level value function (LLVF) approach and the Karush-Kuhn-Tucker (KKT) representation of lower-level optimal solution maps. We also derive upper subdifferential necessary optimality conditions of a new type, which can be essentially stronger than the lower ones in some particular settings. Finally, certain links are established between the obtained necessary optimality conditions for the pessimistic and optimistic versions in bilevel programming.