Practical bilevel optimization. Algorithms and applications (Q1304175)

The main purpose of the book is to present the development and implementation of algorithms for solving bilevel programming problems and inform the reader about some areas of applications of bilevel programming. The book is divided into three main parts. Part I contains summary chapters on linear, integer and nonlinear programming. The aim of this part is to provide a sufficient theoretical background , which is used later to explain the methodological nature of bilevel programming, as well as its theory and algorithms for solving bilevel programming problems. For this purpose, the author explains the principles of the simplex method, the linear complementarity problem, main principles of the duality theory and dual simplex method; the author included also enumerative and cutting planes methods from integer programming and Benders decomposition for mixed integer linear programming problems. In the last chapter of this part, some results of the nonlinear programming theory as well as some methods for solving convex differentiable programming problems are summarized. Part II is devoted to the main topic of the book, i.e. to the theory and algorithms of the bilevel programming. The explanations begin with linear bilevel programming problems, the standard terminology is introduced and some theoretical properties of the problems are derived. Further, five most important algorithms are described and their computational efficiency is compared. Each of the algorithms is designed to find a global optimum. The theory is then extended to include problems with discrete variables and mixed-integer cases. Branch-and-bound, and a specialized algorithm for the zero-one case are suggested as appropriate solution methods for these problems. The next chapters of this part are devoted to the convex and to the general bilevel programming problems with a special emphasis on the convex quadratic case. A variety of solution techniques as for instance penalty methods, steepest descent, rectangular partitioning, subgradient optimization are discussed. If these methods are used to solve nonconvex nondifferentiable problems, only local optima are usually achieved. The rest of Part II is devoted to heuristics (tabu search, genetic algorithms, simulated annealing). Part III deals with applications of bilevel programming in transportation network design, production planning with inexact demand, and government regulation problem associated with the promotion of biofuels. At the end of the book, an extensive list of bibliographic references and index are attached.