519.7 dc21
97-6931
To Pierrette and Marie
Preface
According to a French saying “G´erer, c’est pr´evoir,” which we may trans-
late as “(The art of) Managing is (in) foreseeing.” Now, probability and
statistics have long since taught us that the future cannot be perfectly
forecast but instead should be considered random or uncertain. The aim of
stochastic programming is precisely to find an optimal decision in problems
involving uncertain data. In this terminology, stochastic is opposed to de-
terministic and means that some data are random, whereas programming
refers to the fact that various parts of the problem can be modeled as linear
or nonlinear mathematical programs. The field, also known as optimization
under uncertainty, is developing rapidly with contributions from many dis-
ciplines such as operations research, economics, mathematics, probability,
and statistics. The objective of this book is to provide a wide overview of
stochastic programming, without requiring more than a basic background
in these various disciplines.
Introduction to Stochastic Programming is intended as a first course for
beginning graduate students or advanced undergraduate students in such
fields as operations research, industrial engineering, business administra-
tion (in particular, finance or management science), and mathematics. Stu-
dents should have some basic knowledge of linear programming, elementary
analysis, and probability as given, for example, in an introductory book on
operations research or management science or in a combination of an in-
troduction to linear programming (optimization) and an introduction to
probability theory.
Instructors may need to add some material on convex analysis depending
on the choice of sections covered. We chose not to include such introductory
viii
Preface
material because students’ backgrounds may vary widely and other texts
include these concepts in detail. We did, however, include an introduction
to random variables while modeling stochastic programs in Section 2.1 and
short reviews of linear programming, duality, and nonlinear programming
at the end of Chapter 2. This material is given as an indication of the pre-
requisites in the book to help instructors provide any missing background.
In the Subject Index, the first reference to a concept is where it is defined
or, for concepts specific to a single section, where a source is provided.
In our view, the objective of a first course based on this book is to help
students build an intuition on how to model uncertainty into mathemati-
cal programs, which changes uncertainty brings into the decision process,
what difficulties uncertainty may bring, and what problems are solvable. To
begin this development, the first section in Chapter 1 provides a worked
example of modeling a stochastic program. It introduces the basic con-
cepts, without using any new or specific techniques. This first example can
be complemented by any one of the other proposed cases of Chapter 1,
in finance, in multistage capacity expansion, and in manufacturing. Based
again on examples, Chapter 2 describes how a stochastic model is formally
built. It also stresses the fact that several different models can be built,
depending on the type of uncertainty and the time when decisions must
be taken. This chapter links the various concepts to alternative fields of
planning under uncertainty.
Any course should begin with the study of those two chapters. The sequel
would then depend on the students’ interests and backgrounds. A typical
course would consist of elements of Chapter 3, Sections 4.1 to 4.5, Sections
5.1 to 5.3 and 5.7, and one or two more advanced sections of the instructor’s
choice. The final case study may serve as a conclusion. A class emphasizing
modeling might focus on basic approximations in Chapter 9 and sampling
in Chapter 10. A computational class would stress methods from Chapters
6 to 8. A more theoretical class might concentrate more deeply on Chapter
3 and the results from Chapters 9 to 11.
The book can also be used as an introduction for graduate students
interested in stochastic programming as a research area. They will find
a broad coverage of mathematical properties, models, and solution algo-
rithms. Broad coverage cannot mean an in-depth study of all existing re-
search. The reader will thus be referred to the original papers for details.
Advanced sections may require multivariate calculus, probability measure
theory, or an introduction to nonlinear or integer programming. Here again,
the stress is clearly in building knowledge and intuition in the field. Math-
ematical results are given so long as they are either basic properties or
helpful in developing efficient solution procedures. The importance of the
various sections clearly reflects our own interests, which focus on results
that may lead to practical applications of stochastic programming.