In this directory you will find papers published as Preprints at several universities. Some of the papers are published also in journals in slightly modified versions. ============================================================================= Discrete Bilevel Optimization Problems (dbilopt.dvi, dbilopt.ps) S. Dempe Arbeitsbericht Nr. 12, Februar 1996, Universitaet Leipzig, Wirtschaftswissenschaftliche Fakultaet, Institut fuer 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. ----------------------------------------------------------------------------- On the leader's dilemma and a new idea for attacking bilevel programming problems (lblpphp.dvi, lblpphp.ps) S. Dempe 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. ------------------------------------------------------------------------- Quasidifferentiability of optimal solutions in parametric nonlinear optimization (quasi.dvi, quasi.ps) S. Dempe, D. Pallaschke 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. ---------------------------------------------------------------------------  Applicability of two-level optimization models to issues of environmental policy (frankfu.doc) Paper written in Word6.0 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. ----------------------------------------------------------------------------- Generalized $PC^1$-Functions and their Application to Bilevel Programming Problems (unger1.dvi, unger1.ps) S. Dempe, Freiberg University of Mining and Technology and T. Unger, Technical University of Chemnitz Preprint 97-06, Fakultaet fuer Mathematik und Informatik, Technische Universitaet 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. --------------------------------------------------------------------------- A bundle algorithm applied to bilevel programming problems with non-unique lower level solutions (coap98.dvi, coap98.ps) S. Dempe, Freiberg University of Mining and Technology, Germany 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. -------------------------------------------------------------------------------- The subdifferential of the optimal solution in parametric optimization (sospo.ps, sospo.dvi) S.~Dempe, S.~Vogel TU Bergakademie Freiberg, Fakultaet fuer Mathematik und Informatik, D-09596 Freiberg, Germany Preprint 97-10, Fakultaet fuer 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. ------------------------------------------------------------------------------ A Bundle Trust Region Algorithm for Bilinear Bilevel Programming (BILIN1_1.DVI, BILIN1_1.PS) S. Dempe, Freiberg University of Mining and Technology, Germany J.F. Bard, Graduate Program in Operations Research, University of Texas, Austin, U.S.A. Preprint 99-4 TU Bergakademie Freiberg, Fekult"at f"ur 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. ------------------------------------------------------------ A minimax resource allocation problem with variable resources (GOLST3.dvi, GOLST3.ps) E.G.Gol'stejn, Russian Academy of Sciences, Moscow S. Dempe, Freiberg University of Mining and Technology Preprint TU Bergakademie Freiberg Nr. 2000-03, Fakult"at f"ur 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. -------------------------------------------------------------------- Bilevel programming with knapsack constraints (BILKNAP2.dvi, BILKNAP2.PS) S. Dempe, Freiberg University of Mining and Technology K. Richter, Technical University Chemnitz Preprint TU Bergakademie Freiberg Nr. 2000-05, Fakult"at f"ur 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. --------------------------------------------------------------------------- Bilevel programming with knapsack constraints (BILKNAP1.PS) S. Dempe, K. Richter 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. --------------------------------------------------------------------------- S. Dempe: On the directional derivative of a locally upper Lipschitz continuous point-to-set mapping and its application to optimization problems. In: J. Guddat et al.: Parametric Optimization and Related Topics III, Verlag Peter Lang, 1993, pp. 89-106 (ARTPAROP.PS, ARTPAROP.DVI) ---------------------------------------------------------------------------- S. Dempe: Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints (bibliography.ps, bibliography.dvi,bibliography.pdf) Preprint TU Bergakademie Freiberg Nr. 2003-01, Fakult"at f"ur 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. ---------------------------------------------------------------------------- Stephan Dempe, Vyacheslav Kalashnikov, Roger Z. R\'{\i}os-Mercado: Discrete Bilevel Programming: Application to a Natural Gas Cash-Out Problem (gas_cash-out.pdf, gas_cash-out.ps) Preprint TU Bergakademie Freiberg Nr. 2003-10, Fakult"at f"ur 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. ------------------------------------------------------------------------------ Stephan Dempe, Vyacheslav Kalashnikov: A mixed-discrete bilevel programming problem (mixed.ps, mixed.pdf) 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. ----------------------------------------------------------------------------- Stephan Dempe: Bilevel Programming - A Survey (bilevel_survey.pdf) Preprint TU Bergakademie Freiberg Nr. 2003-11, Fakult"at f"ur 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. ----------------------------------------------------------------------------- S. Dempe, T. Starostina: Sensitivity analysis for linear optimization problem with fuzzy data in objective function (fuzzy_paper.pdf) Preprint TU Bergakademie Freiberg Nr. 2003-09, Fakult"at f"ur 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. --------------------------------------------------------------------------- S. Dempe, S.F. Maharramov: Optimization of discrete control systems with varying structure (maharramov.pdf) Preprint TU Bergakademie Freiberg Nr. 2005-1, Fakult"at f"ur 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. --------------------------------------------------------------------------- S. Dempe, S. Lohse: Inverse Linear Programming (dempe-lohse.pdf) To appear 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. ------------------------------------------------------------------------ A. G. Mersha, S. Dempe: Linear bilevel programming with upper level constraints depending on the lower level solution (Ayalew_paper.pdf) Preprint TU Bergakademie Freiberg, Nr. 2005-5, Fakult"at f"ur 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. ----------------------------------------------------------------------- S. Dempe, N. Gadhi: Necessary optimality conditions for bilevel set optimization problems (Gadhi-dempe.pdf) Preprint TU Bergakademie Freiberg, Nr. 2005-4, Fakult"at f"ur 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. ------------------------------------------------------------------------- S. Dempe, S. Lohse: Beste Strassenbenutzungsgebuehren -- Modelle und ein Optimalitaetstest (Lohse_preprint.pdf) Preprint TU Bergakademie Freiberg, Nr. 2005-6, Fakult"at f"ur Mathematik und Informatik, 2005 ------------------------------------------------------------------------- S. Dempe, S. Lohse: Modelle zur Berechnung einer optimalen Maut (bht_Lohse.pdf) 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. ------------------------------------------------------------------------ S. Dempe, N. Gadhi: Necessary optimality conditions of a D.C. set valued bilevel optimization problem (dempe_gadhi_DC.pdf) Preprint TU Bergakademie Freiberg, Nr. 2006-4, Fakult"at f"ur Mathematik und Informatik, 2006 Abstract: In this paper, we consider a bilevel vector optimization problem where objective and constraints are set valued maps. Our approach consists of using a support function together with the convex separation principle for the study of necessary optimality conditions for D.C bilevel set valued optimization problems. We give optimality conditions in terms of the strong subdifferential of a cone-convex set valued mapping introduced by Baier and Jahn and the weak subdifferential of a cone-convex set valued mapping of Sawaragi and Tanino. The bilevel set valued problem is transformed into a one level set valued optimization problem using a transformation originated by Ye and Zhu. An example which illustrate the usefulness of our result is also given. ---------------------------------------------------------------------------------------------- S. Dempe, T. Starostina: On the solution of fuzzy bilevel programming problems Working Paper, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, September 2007 (bilevel_fuzzy.pdf) 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. ----------------------------------------------------------------------------------------------- S. Dempe, A.B. Zemkoho: A bilevel approach to traffic management in capacitated networks (Preprint 05_08.pdf) Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2008-05 --------------------------------------------------------------------------------------------- Ayalew Getachew Mersha, S. Dempe: Direct Search Algorithm for Bilevel Programming Problems (Ayalew_paper1.pdf) 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. ---------------------------------------------------------------------------------------------- Ayalew Getachew Mersha, S. Dempe: Feasible Direction Method for Bilevel Programming Problem (Ayalew_paper2.pdf) 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. ------------------------------------------------------------------------------------------- S. Dempe, J. Dutta: Is bilevel programming a special case of a mathematical program with complementarity constraints? Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2009-03 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. ------------------------------------------------------------------------------------------------------- S. Dempe, A. Ruziyeva: The Karush-Kuhn-Tucker optimality conditions in fuzzy optimization Preprint, Department of Mathematics and Computer Science, TU Bergakademie Freiberg, Nr. 2010-06 (Ruziyeva2010_06.pdf) 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.