Bilevel Programming Problems | springerprofessional.de

Springer Professional

Top

2015 | Book

Read chapter Read first chapter

Bilevel Programming Problems

Theory, Algorithms and Applications to Energy Networks

Authors: Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Publisher: Springer Berlin Heidelberg

Book Series : Energy Systems

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

This book describes recent theoretical findings relevant to bilevel programming in general, and in mixed-integer bilevel programming in particular. It describes recent applications in energy problems, such as the stochastic bilevel optimization approaches used in the natural gas industry. New algorithms for solving linear and mixed-integer bilevel programming problems are presented and explained.

Advertisement

Table of Contents

Frontmatter

Chapter 1. Introduction

Abstract

After definition of the bilevel optimization problem, focus is on the optimistic and pessimistic formulations for which conditions guaranteeing the existence of an optimal solution are formulated. Using a continuous knapsack problem with right-hand side perturbation in the lower level both formulations are illustrated. In the last part a number of applications of the problem are given.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 2. Linear Bilevel Optimization Problem

Abstract

The linear bilevel optimization problem is considered first. For this some surprising properties are reported: What happens if a constraint on both the upper and the lower level variables is moved from the upper to the lower level problem or one constraint is added which is not active in the lower level problem at an optimal solution? What happens if a variable is added in the lower level? The bilevel optimization problem is a \(NP\)- hard optimization problem but conditions can be formulated guaranteeing that verification of an optimal solution can be done in polynomial time. In the last part, solution algorithms for the linear bilevel optimization problem are formulated either using regions of stability for solutions of the lower level problem or the optimal value reformulation of the bilevel problem.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 3. Reduction of Bilevel Programming to a Single Level Problem

Abstract

Using the Karush-Kuhn-Tucker conditions, generalized equations describing necessary optimality conditions or the optimal value function of the lower level problem, the bilevel optimization problem can be transformed into a single-level optimization problem. Two of these transformations are fully equivalent to the bilevel problem, the MPEC is not. Using these transformations, necessary conditions for local optimal solutions can be formulated: In the case of a strongly stable lower level optimal solution using its directional derivative, using partial calmness in the optimal value function transformation, and applying variational analysis for KKT transformations explicitly using Lagrange multipliers or not. Solution algorithms are formulated and investigated for all reductions.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 4. Convex Bilevel Programs

Abstract

The task to find a best point within the set of optimal solutions of a convex optimization problem is called simple bilevel optimization problem. In general, a necessary optimality condition for a convex simple bilevel problem does not need to be sufficient. An adapted necessary and sufficient optimality condition is derived using tools from cone-convex optimization and a gradient type descent method is suggested which combines the use of a convex combination of both objective functions and projection onto the feasible set. In the second section, a similar algorithm is used to find a best point within the solutions of a variational inequality.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 5. Mixed-Integer Bilevel Programming Problems

Abstract

Here we are faced with two more surprising facts: a global optimal solution of the linear relaxation of the mixed-discrete bilevel problem need not to be globally optimal even if it is feasible and an optimal solution of the optimistic linear bilevel problem does in general not exist. To circumvent the last difficulty, weak optimistic solutions are defined arising if the objective function is minimized over the closure of the feasible set. Optimality conditions can be defined using discontinuous, but piecewise continuously differentiable functions. In the last part, a solution algorithm is described using an outer approximation of the optimal value function of the lower level problem.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 6. Applications to Natural Gas Cash-Out Problem

Abstract

The nature of natural gas implies that imbalances occur between the declared and really extracted amount of gas in a pipeline system. The transmit system operator penalizes the gas shipping company for these imbalances. The task of minimizing the resulting cash flow is modeled as bilevel optimization problem with one Boolean variable in the lower level problem. We report related models, arising in applications, if the Boolean variable is shifted to the upper level problem or when stochastic data are implemented. Solution algorithms and numerical results are presented.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 7. Applications to Other Energy Systems

Abstract

Focus in the first part is on equilibria in a mixed oligopoly in electricity markets, especially a model with a conjectured variations equilibrium. The agents’ conjectures concern the price variations depending upon their production output’s increase or decrease. Besides theoretical questions results of numerical computations are presented. The computation of best tolls for traveling through arcs of a transportation network is modeled as a bilevel optimization problem in the second section. Here, the lower level problem is a multicommodity network flow problem with parametric objective function. An algorithm implementing the filling functions technique is presented. At the end results of a numerical realization of this algorithm are reported.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Chapter 8. Reduction of the Dimension of the Upper Level Problem in a Bilevel Optimization Model

Abstract

Aim of this chapter is a possible reduction of the upper level problem’s dimension. This is necessary for solving the \(\mathcal {NP}\)-hard bilevel optimization problem especially in case of stochastic data. To realize this, a second follower’s problem is composed and the bilevel problem is replaced with one where a parametric Nash equilibrium between two followers is considered in the lower level. The cases of linear and nonlinear bilevel optimization are described in detail. An example is used to illustrate this idea.

Stephan Dempe, Vyacheslav Kalashnikov, Gerardo A. Pérez-Valdés, Nataliya Kalashnykova

Backmatter

Title: Bilevel Programming Problems
Authors: Stephan Dempe
Vyacheslav Kalashnikov
Gerardo A. Pérez-Valdés
Nataliya Kalashnykova
Copyright Year: 2015
Publisher: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-45827-3
Print ISBN: 978-3-662-45826-6
DOI: https://doi.org/10.1007/978-3-662-45827-3