## Introduction to Stochastic ProgrammingThe aim of stochastic programming is to find optimal decisions in problems which involve uncertain data. This field is currently developing rapidly with contributions from many disciplines including operations research, mathematics, and probability. Conversely, it is being applied in a wide variety of subjects ranging from agriculture to financial planning and from industrial engineering to computer networks. This textbook provides a first course in stochastic programming suitable for students with a basic knowledge of linear programming, elementary analysis, and probability. The authors aim to present a broad overview of the main themes and methods of the subject. Its prime goal is to help students develop an intuition on how to model uncertainty into mathematical problems, what uncertainty changes bring to the decision process, and what techniques help to manage uncertainty in solving the problems. The first chapters introduce some worked examples of stochastic programming and demonstrate how a stochastic model is formally built. Subsequent chapters develop the properties of stochastic programs and the basic solution techniques used to solve them. Three chapters cover approximation and sampling techniques and the final chapter presents a case study in depth. A wide range of students from operations research, industrial engineering, and related disciplines will find this a well-paced and wide-ranging introduction to this subject. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction and Examples | 3 |

11 A Farming Example and the News Vendor Problem | 4 |

12 Financial Planning and Control | 20 |

13 Capacity Expansion | 28 |

14 Design for Manufacturing Quality | 37 |

15 Other Applications | 42 |

Uncertainty and Modeling Issues | 49 |

22 Deterministic Linear Programs | 51 |

64 Nonlinear Programming in Simple Recourse Problems | 225 |

65 Other Nonlinear ProgrammingBased Methods | 231 |

Multistage Stochastic Programs | 233 |

71 Nested Decomposition Procedures | 234 |

72 Quadratic Nested Decomposition | 244 |

73 Other Approaches to Multiple Stages | 251 |

Stochastic Integer Programs | 253 |

82 Simple Integer Recourse | 262 |

23 Decisions and Stages | 52 |

24 TwoStage Program with Fixed Recourse | 54 |

25 Random Variables and Risk Aversion | 61 |

26 Implicit Representation of the Second Stage | 63 |

27 Probabilistic Programming | 64 |

28 Relationship to Other DecisionMaking Models | 67 |

29 Short Reviews | 73 |

Basic Properties | 81 |

Basic Properties and Theory | 83 |

31 TwoStage Stochastic Linear Programs with Fixed Recourse | 84 |

32 Probabilistic or Chance Constraints | 103 |

33 Stochastic Integer Programs | 109 |

34 TwoStage Stochastic Nonlinear Programs with Recourse | 122 |

35 Multistage Stochastic Programs with Recourse | 128 |

The Value of Information and the Stochastic Solution | 137 |

42 The Value of the Stochastic Solution | 139 |

43 Basic Inequalities | 140 |

44 The Relationship between EVPI and VSS | 141 |

45 Examples | 144 |

46 Bounds on EVPI and VSS | 145 |

Solution Methods | 153 |

TwoStage Linear Recourse Problems | 155 |

51 The LShaped Method | 156 |

52 Feasibility | 163 |

53 The Multicut Version | 166 |

54 Bunching and Other Efficiencies | 169 |

55 Inner Linearization Methods | 174 |

56 Basis Factorization Methods | 179 |

57 Special CasesSimple Recourse and Network Problems | 192 |

Nonlinear Programming Approaches to TwoStage Recourse Problems | 199 |

62 The Piecewise Quadratic Form of the LShaped Method | 206 |

63 Methods Based on the Stochastic Program Lagrangian | 215 |

83 Binary FirstStage Variables | 268 |

84 Other Approaches | 276 |

Approximation and Sampling Methods | 283 |

Evaluating and Approximating Expectations | 285 |

91 Direct Solutions with Multiple Integration | 286 |

92 Discrete Bounding Approximations | 288 |

93 Using Bounds in Algorithms | 296 |

94 Bounds in ChanceConstrained Problems | 301 |

95 Generalized Bounds | 305 |

96 General Convergence Properties | 323 |

Monte Carlo Methods | 331 |

101 General Results for Sampled Problems | 332 |

102 Using Sampling in the LShaped Method | 335 |

103 Stochastic QuasiGradient Methods | 343 |

Uses with Analytical and Empirical Observations | 349 |

Multistage Approximations | 353 |

111 Bounds Based on the Jensen and EdmundsonMadansky Inequalities | 354 |

112 Bounds Based on Aggregation | 359 |

113 Bounds Based on Separable Responses | 362 |

114 Bounds for Specific Problem Structures | 366 |

A Case Study | 373 |

Capacity Expansion | 375 |

121 Model Development | 376 |

122 Demand Distribution Modeling | 382 |

123 Computational Comparisons | 383 |

Sample Distribution Functions | 385 |

A2 Continuous Random Variables | 386 |

387 | |

Author Index | 411 |

415 | |

### Other editions - View all

### Common terms and phrases

algorithm approach approximation assume basic capacity Chapter components computation consider continuous random variables convergence convex function convex hull corresponding cost decomposition defined demand describe deterministic equivalent discrete random variable dual EVPI example Exercise expected value extreme point feasibility cut feasible solution finite number first-stage decisions formulation given go to Step inequality infeasible inner linearization integer interior point method iterations L-shaped method Lagrangian linear program Louveaux lower bound matrix multipliers nonanticipative nonlinear programming objective function objective value obtain optimal solution optimal value optimality cuts period piecewise linear plant possible primal probabilistic constraints probability measure procedure Proof properties quadratic random variables random vector realizations recourse function regularized decomposition right-hand side s.t. Ax sampling scenarios Section simplex solve stage stochastic linear program stochastic program subgradient sugar beets Suppose Theorem tion upper bound yields

### Popular passages

Page 392 - Decision Problems Under Risk and Chance Constrained Programming: Dilemmas in the Transition'," Management Sci., 29, 6 (June 1983).

Page 409 - Convergence of convex functions, variational inequalities and convex optimization problems" in: RW Cottle, F. Giannessi and J.-L. Lions, Eds., Variational Inequalities and Complementarity Problems (John Wiley, Inc., New York, NY, 1980a) pp. 375-404. [329] RJ-B Wets, "Stochastic multipliers, induced feasibility and nonanticipativity in stochastic programming" in: MAH Dempster, Ed., Stochastic Programming (Academic Press, New York, NY, 1980b).

Page 387 - A combined phase I-phase II projective algorithm for linear programming," Mathematical Programming, 43 (1989), pp.

Page 409 - Large-scale linear programming techniques in stochastic programming" in: Y. Ermoliev and R. Wets, Eds., Numerical Techniques for Stochastic Optimization (Springer- Verlag, Berlin, 1988). [333] RJ-B Wets, "Stochastic programming" in: GL Nemhauser, AHG Rinnooy Kan, and MJ Todd, Eds., Optimization (Handbooks in Operations Research and Management Science; Vol.

Page 409 - Algorithms for frames and lineality spaces of cones," Journal of Research of the National Bureau of Standards — B Mathematics and Mathematical Physics, Vol.

Page 409 - Programming under uncertainty: the equivalent convex program," SIAM Journal on Applied Mathematics 14 (1966) pp. 89-105. [326] RJ-B Wets, "Characterization theorems for stochastic programs," Mathematical Programming 2 (1972) pp.