Stochastic linear programming. Models, theory, and computation
This is a graduate text in optimisation whose main emphasis is in stochastic programming. The book is clearly written. The main stochastic models and programs are discussed at a high mathematical theoretical level while there are mentions to real life applications. The reader needs to have an adequate background of probability theory and optimisation. The authors are well known specialists with a large list of contributions in the theme. Stochastic Linear Programming (SLP) is emerging, as an indispensable tool for tackling the study of large sets of real life problems arising nowadays. The number of practical experiences, in its application to energy management, environmental, finances, production planning and other important areas, is growing. This is a good book for providing mathematicians, economists and engineers with an almost complete start up information for working in the field. I heartily welcome its publication. After an introduction the realm of the book begins, in Chapter 1, with the basics from linear programming, where the indispensable elements of algebra and geometry are presented. Later it goes to the simplex method, one of the most important tools in optimisation. We find there the basic concepts of decomposition (dual, nested, regularization) and on interior point methods. A discussion on nonlinear programming is also developed for guaranteeing the knowledge needed in the sequel. The second chapter is called single stage SLP-models. The authors introduce the related probability models and decision problems arising in recourse models. The different classes of SLP models are described and Lagrangian relaxation methods are discussed. Continuing with the convexity of the programs, the basic properties of the feasible sets, the considerations for the finite discrete distribution cases (the separate probability functions, the side stochastic right hand) as particular cases. The analysis of the behaviour of the mathematical models under normality, or when a certain stable distribution is describing the phenomena, is developed. The Cauchy distribution is used for exemplifying. The distribution free approach is also presented. The results, when independence is present, are also developed. A similar study is made for the expectation and deviation models. The results discussed allow to present some current financial problems, as the study of risks, which can be tackled through the use of SLP procedures. The title of Chapter 3 is Multistage SLP models. It is a natural sequel to the previous chapter. The dynamical nature of recourse problems is established in its first section for the general case. In Section 2 the authors present the 2-stage problem and establish particular models that arise in the investigation of real life problems: Completely fixed recourse and simple recourse. The remainder of the section contains results on the optimal value yielding characteristics of the expected value problem under some assumptions on the involved linear affine mappings. The third section revisits the general Multistage SLP model introduced initially. The finite discrete distribution case is studied. It yields the scenario approach and justifies the use of scenarios trees. This is the theme of Subsection 3.1. The non-discrete distribution case is the content of the natural sequel in Subsection 3.2, where the usefulness of discretizing, makes possible the use of adequate refinements of partitions for deriving scenarios trees. In Chapter 4 a recount of the genesis, philosophy and characteristics of the existing algorithms for the solution of SLP is made. The sections present algorithms as functions of the SLP classes studied in the book. Section 2 is devoted to algorithms for single stage models with separate probability functions, corresponding to the program in Section 2.3 of Chapter 2. The third section provides a similar content for single stage models with joint probability functions (Chapter 2, Section 2.6). Some numerical considerations point out the characteristics of the nonlinear problems appearing in the case of dealing with the distributions that are non-degenerate normal. The need of the Slater point existence in cutting plane methods in the algorithms implemented is discussed and its role illustrated. The authors note the distribution-free property present in the derivation of bounds for the probability distribution. Subsection 3.5 introduces algorithms for SLP related with the multivariate normal distribution by describing how Monte Carlo methods behave in the non-degenerate case. Section 3.6 deals with finite discrete distributions with joint probability function and the role of disjunctive programming in the solution of these SLP problems. Section 4 presents algorithm for the theme treated in Chapter 2 Section 4, while Section 5 plays the same role with respect to Section 3 of that chapter. On the other hand Section 5 discusses the behaviour of algorithms the Section 2.3 and Section 6 with 2.5. Section 7 is concerned with models presented in Chapter 3 sections and Subsections 2.2, 2.3.1, 4.8, 2.0, 2.51 where stochastic algorithms are presented. Section 8 is devoted to other algorithms presented in Chapter 3 Section 3. Continuing with the exposition of algorithms for SLP Section 9 presents 5 modelling systems highlighting their main features. Among them is the system developed by the authors, which is described at large. It is available in the web. At the end of each section a guide for dealing with the existing software is provided. A list of 314 entries is given. It is evident that this book will constitute an obligatory reference source for the specialists of the field.
scientific article; zbMATH DE number 2152357