Birge / Louveaux Introduction to Stochastic Programming

2. Auflage 2011
ISBN: 978-1-4614-0237-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 500 Seiten

Reihe: Springer Series in Operations Research and Financial Engineering

The 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. At the same time, it is now 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.

In this extensively updated new edition there is more material on methods and examples including several new approaches for discrete variables, new results on risk measures in modeling and Monte Carlo sampling methods, a new chapter on relationships to other methods including approximate dynamic programming, robust optimization and online methods.
The book is highly illustrated with chapter summaries and many examples and exercises. Students, researchers and practitioners in operations research and the optimization area will find it particularly of interest.


Review of First Edition:
'The discussion on modeling issues, the large number of examples used to illustrate the material, and the breadth of the coverage make 'Introduction to Stochastic Programming' an ideal textbook for the area.' (Interfaces, 1998)

John R. Birge, is a Jerry W. and Carol Lee Levin Professor of Operations Management at the University of Chicago Booth School of Business. François Louveaux is a Professor at the University of Namur(FUNDP) in the Department of Business Administration

Autoren/Hrsg.

Birge, John R.

Louveaux, François

Inhaltsverzeichnis

1;Preface;8
2;Preface to the First Edition;12
3;Contents;16
4;Notation;22
5;Part I Models;28
5.1;1 Introduction and Examples;29
5.1.1;1.1 A Farming Example and the News Vendor Problem;30
5.1.1.1;a. The farmer's problem;30
5.1.1.2;b. A scenario representation;32
5.1.1.3;c. General model formulation;36
5.1.1.4;d. Continuous random variables;37
5.1.1.5;e. The news vendor problem;41
5.1.2;1.2 Financial Planning and Control;46
5.1.3;1.3 Capacity Expansion;54
5.1.4;1.4 Design for Manufacturing Quality;61
5.1.5;1.5 A Routing Example;66
5.1.5.1;a. Presentation;66
5.1.5.2;b. Wait-and-see solutions;68
5.1.5.3;c. Expected value solution;69
5.1.5.4;d. Recourse solution;70
5.1.5.5;e. Other random variables;72
5.1.5.6;f. Chance-constraints;73
5.1.6;1.6 Other Applications;74
5.2;2 Uncertainty and Modeling Issues;81
5.2.1;2.1 Probability Spaces and Random Variables;81
5.2.2;2.2 Deterministic Linear Programs;83
5.2.3;2.3 Decisions and Stages;83
5.2.4;2.4 Two-Stage Program with Fixed Recourse;85
5.2.4.1;a. Fixed distribution pattern, fixed demand,ri, vj, tij stochastic;88
5.2.4.2;b. Fixed distribution pattern, uncertain demand;89
5.2.4.3;c. Uncertain demand, variable distribution pattern;90
5.2.4.4;d. Stages versus periods; Two-stage versus multistage ;91
5.2.5;2.5 Random Variables and Risk Aversion;92
5.2.6;2.6 Implicit Representation of the Second Stage;94
5.2.6.1;a. A closed form expression is available for Q(x);95
5.2.6.2;b. For a given x, Q(x) is computable;96
5.2.7;2.7 Probabilistic Programming;97
5.2.7.1;a. Deterministic linear equivalent: a direct case;97
5.2.7.2;b. Deterministic linear equivalent: an indirect case;98
5.2.7.3;c. Deterministic nonlinear equivalent: the case of random constraint coefficients;99
5.2.8;2.8 Modeling Exercise;100
5.2.8.1;a. Presentation;100
5.2.8.2;b. Discussion of solutions;102
5.2.9;2.9 Alternative Characterizations and Robust Formulations;110
5.2.10;2.10 Relationship to Other Decision-Making Models;113
5.2.10.1;a. Statistical decision theory and decision analysis ;113
5.2.10.2;b. Dynamic programming and Markov decision processes;115
5.2.10.3;c. Machine learning and online optimization;116
5.2.10.4;d. Optimal stochastic control;117
5.2.10.5;e. Summary;119
5.2.11;2.11 Short Reviews;120
5.2.11.1;a. Linear programming;120
5.2.11.2;b. Duality for linear programs;122
5.2.11.3;c. Nonlinear programming and convex analysis;123
6;Part II Basic Properties;127
6.1;3 Basic Properties and Theory;128
6.1.1;3.1 Two-Stage Stochastic Linear Programs with Fixed Recourse;128
6.1.1.1;a. Formulation;128
6.1.1.2;b. Discrete random variables;130
6.1.1.3;c. General cases;134
6.1.1.4;d. Special cases: relatively complete, complete,and simple recourse;138
6.1.1.5;e. Optimality conditions and duality;140
6.1.1.6;f. Stability and nonanticipativity;143
6.1.2;3.2 Probabilistic or Chance Constraints;149
6.1.2.1;a. General case;149
6.1.2.2;b. Probabilistic constraints with discrete random variables;155
6.1.3;3.3 Stochastic Integer Programs;160
6.1.3.1;a. Recourse problems;160
6.1.3.2;b. Simple integer recourse;165
6.1.3.3;c. Probabilistic constraints;171
6.1.4;3.4 Multistage Stochastic Programs with Recourse;174
6.1.5;3.5 Stochastic Nonlinear Programs with Recourse;181
6.2;4 The Value of Information and the Stochastic Solution;187
6.2.1;4.1 The Expected Value of Perfect Information;187
6.2.2;4.2 The Value of the Stochastic Solution;189
6.2.3;4.3 Basic Inequalities;190
6.2.4;4.4 The Relationship between EVPI and VSS;191
6.2.4.1;a. EVPI = 0 and VSS =0;192
6.2.4.2;b. VSS = 0 and EVPI=0;193
6.2.5;4.5 Examples;194
6.2.6;4.6 Bounds on EVPI and VSS;195
7;Part III Solution Methods;202
7.1;5 Two-Stage Recourse Problems;203
7.1.1;5.1 The L-Shaped Method;204
7.1.1.1;a. Optimality cuts;206
7.1.1.2;b. Feasibility cuts;213
7.1.1.3;c. Proof of convergence;218
7.1.1.4;d. The multicut version;220
7.1.2;5.2 Regularized Decomposition;224
7.1.3;5.3 The Piecewise Quadratic Form of the L-shaped Methods;232
7.1.4;5.4 Bunching and Other Efficiencies;239
7.1.4.1;a. Full decomposability;240
7.1.4.2;b. Bunching;241
7.1.5;5.5 Basis Factorization and Interior Point Methods;244
7.1.6;5.6 Inner Linearization Methods and Special Structures;259
7.1.7;5.7 Simple and Network Recourse Problems;264
7.1.8;5.8 Methods Based on the Stochastic Program Lagrangian;275
7.1.9;5.9 Additional Methods and Complexity Results;284
7.2;6 Multistage Stochastic Programs;286
7.2.1;6.1 Nested Decomposition Procedures;287
7.2.2;6.2 Quadratic Nested Decomposition;297
7.2.3;6.3 Block Separability and Special Structure ;303
7.2.4;6.4 Lagrangian-Based Methods for Multiple Stages;305
7.3;7 Stochastic Integer Programs;309
7.3.1;7.1 Stochastic Integer Programs and LP-Relaxation;309
7.3.2;7.2 First-stage Binary Variables;311
7.3.2.1;a. Improved optimality cuts;314
7.3.2.2;b. Example with continuous random variables;319
7.3.3;7.3 Second-stage Integer Variables;322
7.3.3.1;a. Looking in the space of tenders;323
7.3.3.2;b. Discontinuity points;325
7.3.3.3;c. Algorithm;326
7.3.4;7.4 Reformulation;332
7.3.4.1;a. Difficulties of reformulation in stochastic integer programs;332
7.3.4.2;b. Disjunctive cuts;334
7.3.4.3;c. First-stage dependence;336
7.3.4.4;d. An algorithm;337
7.3.5;7.5 Simple Integer Recourse;339
7.3.5.1;a. restricted to be integer;342
7.3.5.2;b. The case where S=1, not integral;345
7.3.6;7.6 Cuts Based on Branching in the Second Stage;346
7.3.6.1;a. Feasibility cuts;346
7.3.6.2;b. Optimality cuts;349
7.3.7;7.7 Extensive Forms and Decomposition;351
7.3.8;7.8 Short Reviews;354
7.3.8.1;a. Branch-and-bound;354
7.3.8.2;b. A simple example of valid inequalities;355
7.3.8.3;c. Disjunctive cuts;356
8;Part IV Approximation and Sampling Methods;359
8.1;8 Evaluating and Approximating Expectations;360
8.1.1;8.1 Direct Solutions with Multiple Integration;361
8.1.2;8.2 Discrete Bounding Approximations;365
8.1.3;8.3 Using Bounds in Algorithms;371
8.1.4;8.4 Bounds in Chance-Constrained Problems;376
8.1.5;8.5 Generalized Bounds;382
8.1.5.1;a. Extensions of basic bounds;382
8.1.5.2;b. Bounds based on separable functions;386
8.1.5.3;c. General-moment bounds;391
8.1.6;8.6 General Convergence Properties;400
8.2;9 Monte Carlo Methods;407
8.2.1;9.1 Sample Average Approximation and Importance Samplingin the L-Shaped Method;408
8.2.2;9.2 Stochastic Decomposition;413
8.2.3;9.3 Stochastic Quasi-Gradient Methods;417
8.2.4;9.4 Sampling Methods for Probabilistic Constraints and Quantiles;422
8.2.5;9.5 General Results for Sample Average Approximation and Sequential Sampling;427
8.3;10 Multistage Approximations;434
8.3.1;10.1 Extensions of the Jensen and Edmundson-Madansky Inequalities;435
8.3.2;10.2 Bounds Based on Aggregation;439
8.3.3;10.3 Scenario Generation and Distribution Fitting;443
8.3.4;10.4 Multistage Sampling and Decomposition Methods;449
8.3.5;10.5 Approximate Dynamic Programming and Special Cases;453
8.3.5.1;a. Network revenue management;455
8.3.5.2;b. Vehicle allocation problems;456
8.3.5.3;c. Piecewise-linear separable bounds;458
8.3.5.4;d. Nonlinear bounds and a production planning example;461
8.3.5.5;e. Extensions;463
8.4;Sample Distribution Functions;466
8.4.1;A.1 Discrete Random Variables;466
8.4.2;A.2 Continuous Random Variables;467
8.5;References;468
8.6;Author Index;487
8.7;Subject Index;492