Stochastic programming
Most decisions are made
under uncertainty. In many aspects of life we rely on rules-of-thumb, or
heuristics. We leave home at a time we regard as an optimal trade-off between
the waiting time at the bus stop, and the probability of missing the bus. We
determine our driving-speed as a tradeoff between driving fast and getting
there quickly, and driving slowly, getting there safely. Very often the
heuristics serve us well. But some cases are too difficult or too important to
be left to heuristics, which are known to have many biases. In those cases we
have to turn to some methodology to aid our decisions. Stochastic programming
is one of those.
Technically speaking,
stochastic programming (where "programming" means
"planning") is mathematical programming under uncertainty, that is,
any mathematical program where one or more of the coefficients are not fully
known at the time of decision making. The randomness may stem from unknown
prices, uncertain demand, varying quality of raw materials or random behavior
of operators, to mention but a few examples. Stochastic programming, as a
discipline, has several major facets:
The mathematics of stochastic programming
The
algorithmic aspects of how to solve stochastic programs
The numerics
of implementing the algorithms
The
formulation of optimization models where random variables play a major role.
The
recognition of a problem that can effectively be analyzed by stochastic
programming.
So stochastic programming
is a problem class. One of the ways of solving a stochastic program is
by means of stochastic dynamic programming. And stochastic dynamic programming
is a solution procedure, not a problem class. This may be a confusing
use of words, but there is not much we can do about the confusion. Stochastic
programming is therefore not the counterpart of linear programming, integer
programming or non-linear programming (as one may believe when reading for
example conference programs), but the counterpart of deterministic
programming. So we have stochastic linear programming, stochastic integer
programming and stochastic non-linear programming. Stochastic programs can be
solved by a multitude of methods, most of which are adjustments of methods
known from deterministic programming.
I have been interested in
most of the aspects of stochastic programming listed above. But my mathematical
contributions are very limited, and my numerical efforts non-existing. In 1994
I co-authored a textbook on stochastic programming with Peter
Kall of Universität Zürich. It was the world’s first textbook on
stochastic programming, as we understand the term today. The book wraps up the
basics of the mathematics and algorithmics of the field, and starts on a
discussion of modelling. The book was published on Wiley, but is no longer
under copyright. You can now download
the book for free.
My interests today are more
focused on modelling and models. I just finished a textbook on the art of
modelling when facing decisions under uncertainty. The focus is not very mathematical,
and the text is not a stochastic programming text. The issue is rather, what is
decision-making under uncertainty? What do we know about how people make
decisions under uncertainty? How does economic theory treat the issue (option
theory and utility theory)? And what does operations research do? How do you
pass from a deterministic to a stochastic model, and what may go wrong? In
particular, why can’t we use sensitivity analysis, what-if-analysis,
parametric analysis (or whatever is the favourite term)? Much of this is based
on my article in Operations Research: Decision making under uncertainty: Is
sensitivity analysis of any use?
In addition to the
principal issues of models and modelling, I am interested in modelling decision
problems where uncertainty is of major importance. My main application areas
are:
Stochastic service network design. The issue
here is that it is practically impossible to solve (to some extent even formulate)
meaningful stochastic network design models. So what can we do when we know
that the problems are infested with uncertainty and the solutions that come out
of deterministic models are very inflexible? I have just started a walk down
this part together with my new doctoral student Arnt-Gunnar Lium and
Portfolio
management in finance. This is work in the tradition of John Mulvey of
Princeton University, William Ziemba of the University of British Columbia,
Michael Dempster of Cambridge University and Stavros Zenios of the University
of Cyprus, to mention some of the major early contributors. My work is in close
cooperation with my former doctoral student Kjetil Høyland and his employer,
Gjensidige-NOR Asset Management. Our most original contribution so far has been
on scenario generation. A hedge fund based on a stochastic programming model
has been in operation since early 1999.
Portfolio management in the energy sector. The
Norwegian electricity market was deregulated in 1991. As a result, the
(hydro-based) producers face not only uncertain inflows, but also uncertain
prices. A financial market has been created to help the producers manage their
risk. Together with, among others, my former doctoral student, Associate
Professor Stein-Erik Fleten
and Professor William Ziemba of the
Erling
Pettersen started his doctoral work in January 2000. He was also financed by
EnFO (now EBL) and the Norwegian Research Council. His subject is the end user
markets in electricity. He spent 2001 with Andy Philpott in
Project scheduling as a stochastic dynamic
decision problem. As a mathematical programmer I feel particularly bad about
what our field has delivered in project scheduling. While a major focus of
project scheduling is randomness, the tools we provide are all deterministic in
nature. We use terms such as critical path, delay and slack, all focusing on
randomness, and all meaningless in a stochastic world. This work is has been
done in cooperation with my former doctoral student Trond Jørgensen who defended
his thesis in 1999.
Strategic planning in the telecommunications area. This work has been
done in cooperation with my former doctoral students Asgeir
Tomasgard (now SINTEF Industrial Management, Economics and Logistics and
NTNU) and Nils Jacob Berland (now Pantarei), Shane Dye
(the
Much of this work is
closely related to scenario based planning, one of my major interests.