Birge J.R., Louveaux F. Introduction to Stochastic Programming

Подождите немного. Документ загружается.

444 10 Multistage Approximations

where

is the support set of the random variables. Note that if we drop the non-

linear term in the objective and replace

in the constraints with a ﬁxed valued

of E[ξ] , then we can obtain a lower bound on the optimal objective value in (5.9)

(see Birge and Wets [1986]). We should note that in some cases, we may not have a

solution to (5.11)for ±e

but may only have a solution for +e

, e.g. In this case,

t+1

could be constrained to be less than the minimum possible value of ξ

In (5.13), we are solving to determine a centering point,

, that obtains mini-

mum cost if we assume the response to any variation from

is a solution of (5.11).

By allowing some variation of the choice of centering point, a “best” approximation

of this type is found. The value of (5.13) is an upper bound because the composi-

tion of the x

solutions from (5.13)andthe X

values used in the z terms yield a

feasible solution for all

This procedure may also be implemented as responses to several scenarios. In

this case, the random vectors are partitioned as in Section 10.1. The partitions may

also be part of the higher-level optimization problem so that in some way a “best”

partition can be found. The points used within the partitions may be chosen as ex-

pected values, in which case the solution without penalty terms is again a lower

bound on the optimal objective value. For an upper bound, this vector may be al-

lowed to take on any value in the partition.

The use of multiple scenarios enters directly into the progressive hedging ap-

proach of Rockafellar and Wets (see Section 5.3). This can be used to solve the top-

level problem and to approach a solution that is optimal for a given set of partitions

and the piecewise linear penalty structure presented here. Computations are then

restricted to optimizing separable nonlinear functions subject to linear constraints.

Implementations can be based on previous procedures (such as decomposition).

The basic framework for the upper bounding procedures given earlier is to con-

struct a feasible solution that is easily integrated. Other procedures for constructing

such feasible responses are possible. For example, Wallace and Yan [1993] sup-

pose two types of restrictions of the set of solutions to obtain bounds. The ﬁrst is

to suppose only a subset of variables is used within a period, as, for example, with

the penalty terms used for aggregation bounds in Section 10.2. The other approach

is to suppose that all realizations from period to period must meet some common

constraint on values passed between periods. This procedure effectively divides the

multistage problem into a sequence of two-stage problems. It appears to work well

on problems with many stages.

d. Nonlinear bounds and a production planning example

As noted earlier, many multistage stochastic program approximations can take ad-

vantage of the speciﬁc problem structure. For Example 2 in Section 10.2, we consid-

ered a basic production problem that allows the construction of bounds on optimal

primal and dual variables that can then be used in constructing optimal objective

value bounds as in (2.7). Other bounds and approximationsusing similar production

10.5 Approximate Dynamic Programming and Special Cases 445

problem structures are also possible. We explore some of those bounds developed

by Ashford [1984], following Beale, Forrest, and Taylor [1980], and Bitran and

Yanasse [1984], and Bitran and Sarkar [1988]. These bounds can be viewed as ex-

tensions of the aggregation-type bounds in Section 10.2.

The ﬁrst type of extension of the production problem we consider is the model

used in Ashford [1984] which is a slight generalization of (2.8). It is also an exten-

sion of similar work by Beale, Forrest, and Taylor [1980] on a production problem

similar to (2.8). The model is to

minz = E



∑

t=1

(−c

(ξ) −q

(ξ))



s. t. T

t−1

−y

≤ ξ

, a.s., t = 1,...,H ,

≥ l

, u

≥ x

≥ 0 , a.s., t = 1,...,H ,

(5.14)

where x

represents production and related variables and y

represents the state

(e.g., inventory) after realizing demands, ξ

. Both variables are bounded, although

may only have trivial bounds. One upper bound directly analogous to that in

Theorem 3 can be constructed using this structure (see Exercise 1).

A lower bound on the optimal value of (5.14) can be obtained simply by substi-

tuting expected values for the random elements in (5.14). Ashford also presents an

improved lower bound, however, that forms the basis for an approximation proce-

dure. This bound consists of solving a reduced problem:

min z

RED

,...,G

∑

t=1

(−c

−q

)

s. t. T

t−1

−w

, t = 1,...,H ,

−y

−w

≤−f

−l

) , t = 1,...,H ,

≥ x

≥ 0 , a.s., t = 1,...,H ,

(5.15)

where the G

are m

-vectors of given distribution functions, G

, i = 1,...,m

and f

=(f

,..., f

) , with

(



−

∞

(

)dG

(

) , (5.16)

for i = 1,...,m

The bound in (5.15) is chosen by ﬁrst determining the distribution function, G

If G

∗

is the vector of distribution functions of ZT

t−1

t−1,∗

+ W

t,∗

−ξ

for an

optimal solution (y

∗

) of (5.14), then the following theorem holds.

Theorem 4. The solution z

RED

∗

,...,G

∗

) provides a lower bound on the optimal

solution z

∗

in (5.14) and z

RED

∗

,...,G

∗

) ≥ z(

) , the solution of the expected

value problem, i.e., (5.14) with all random variables replaced by their expectations.

Proof:Exercise2.

446 10 Multistage Approximations

It is possible to make the approximation in (5.15) into a deterministic equivalent

of (5.14) if appropriate penalties are placed on the violation of bound constraints on

, but the calculation of this and of the bound given by Theorem 1 requires infor-

mation about the optimal solutions which is not known. Another bound is, however,

obtainable by substituting G

(t) , the distribution function vector, corresponding to

(ξ

−

) (see Exercise 3).This represents the beginning of an approximation when

the ξ

vectors are normally distributed. The approximation successively estimates

parameters of a normal approximation of the distribution of T

t−1

t−1,∗

t,∗

−ξ

from t to t + 1 . This procedure continues until little improvement occurs in this

updating procedure. Computational results with this procedure show signiﬁcant sav-

ings over dynamic programming calculations.

This process can be viewed as a form of dynamic programming approximation

using the input to each period’s decisions as the quantity, T

t−1

t−1,∗

t,∗

−ξ

In this way, it is also similar to the response method given above. An alternative

approach is to build approximations of the value function from period to period.

One application to problems with uncertainties in the W

matrix in (5.14) appears

in Beale, Dantzig, and Watson [1986]. The bounds developed by Bitran et al. follow

these production examples closely. The model is again of the form in (2.8).

e. Extensions

Other structures can also yield bounds in speciﬁc cases. For PERT networks (see,

e.g., Taha [1992]), for example, a typical problem is to balance the beneﬁts of early

completion against the possible penalty costs of exceeding a due date or promise

date. In these problems, a natural separation occurs that allows calculation despite

the interconnected structure of paths and possibly correlated times. Klein Haneveld

[1986] considers bounds on expected tardiness penalties with mean constraints.

Maddox and Birge extend this analysis to bounds with second moment informa-

tion (Birge and Maddox [1995, 1996]) and to bounding probabilities of tardiness

(Maddox and Birge [1991]).

The basic principle throughout this and previous chapters on approximations is

to use convexity of objective and constraints. Relax the problem and substitute ex-

pectations properly to obtain a lower bound. Restrict the problem and maintain a

feasible solution (as perhaps a combination of extremal solutions) to obtain an up-

per bound. Many more bounding approximations are possible based on these fun-

damental observations.

Exercises

1. Show that the ADP estimate satisﬁes the inequality, E[˜z

] ≤ z

∗

, for the multi-

stage stochastic linear program with randomness only in h

and T

10.5 Approximate Dynamic Programming and Special Cases 447

2. Show that ˆz ≤ z

∗

for the bid-price linear program (5.7).

3. Show that the alternative booking limit disaggregate solution provides a sharper

upper bound than the bound using Theorem 3.

4. Show that (5.4) provides a sharper lower bound on (5.6) than the bid-price linear

program (5.7).

5. Consider a network revenue management model with A =



110

101



, c

[−200 −150 −100]

,and d

= 1fori = 1,2,3 with probability 0.5, 0.3,

and 0.4 respectively with b

=[1510]

.Let H = 20 .

(a) Solve the bid-price linear program (5.7) and the ADP linear approximation

(5.4) with 100 random sample paths to obtain lower bound estimates on z

∗

(b) Construct upper bounds using (i) Theorem 3 for the bid-price linear pro-

gram; (ii) the modiﬁed booking limit upper bound.

program in each period; (ii) re-solving the ADP linear approximation (5.4);

(iii) using the probability interpretation in the re-solving step as in Jasin and

Kumar [2010].

6. Use the separable function approach and (5.12) to construct an upper bound on

Example 1 with uniform demand distributions.

7. Let A

be the matrix composed of the positive elements of W

in (5.14) (with

zeros elsewhere). Use this to construct a bound on any feasible dual variable

value with

∑



∏

−1

s=t

)



,where

∏

t−1

s=t

)

= I . Combine this

with Theorem 3 to obtain an upper bound on the optimal objective value using

the solution to the mean value problem.

8. Prove Theorem 4.

9. Show that z

RED

,...,G

) ≤ z

∗

10. To construct a lower bound for nodal recourse, assume a projected value, ˆy

(i)

of y

(i) (as, e.g., an average of incoming and outgoing loads). Find an expres-

sion (in terms of the demand distributions on the ranked full load alternatives)

for the expected value (assuming linearized future costs) of an additional vehi-

cle beyond ˆy

(i) . Show that this procedure gives a lower bound on (5.8)when

t = 1.

11. Show how an upper bounding linearization can be constructed for (5.8)usinga

linearization of Q

t+1

) . (Note: You can assume a constant number of total

vehicles.)

12. Consider a three-period example with ﬁve total vehicles, three nodes (cities),

and salvage values, c

(1)=−2, c

(2)=−1,and c

(3)=−4 . Currently, two

vehicles are at A , two vehicles are at B , and one vehicle is at C . Suppose

demand in each period is uniform on the integers from zero to

max

(ij) ,where

max

(ij) has the following values:

448 10 Multistage Approximations

To j = 12 3

From i =

1023

2202

3330.

Suppose the costs (negative of proﬁts) on each route for a full truck are

To j = 123

From i =

10−1 −2

2 −10−3

3 −2 − 30.

Empty load costs are

To j = 12 3

From i =

1012

2103

3230.

Use the lower and upper bounding procedures in Exercises 4 and 5 to construct

upper and lower bounds on (5.8) for these data.

Appendix A

Sample Distribution Functions

This appendix gives the basic distributions used in the text. We provide their means

and variances. Tables of numerical data for these distributions are easily available

on the web. One such website is http://stattrek.com/.

A.1 Discrete Random Variables

Uniform: U[1, n]

P(ξ = i)=

, i = 1,...,n , n ≥1 ,

with E[ξ]=

n+1

and Var[ξ]=

−1

Binomial: Bi(n, p)

P(ξ = i)=





(1 − p)

n−i

, i = 0,1,...,n ;0< p < 1 ,

with E[ξ]=np and Var[ξ]=np(1 − p) .

Poisson: P(

)

P(ξ = i)=e

−

> 0 , i = 0,1,... ,

with E[ξ]=

and Var[ξ]=

J.R. Birge and F. Louveaux Introduction to Stochastic Programming, Springer Series 449

in Operations Research and Financial Engineering, DOI 10.1007/978-1-4614-0237-4,

 Springer Science+Business Media, LLC 2011

450 A Sample Distribution Functions

A.2 Continuous Random Variables

Uniform: U[0, a]

f (

, 0 ≤

≤ a , a > 0 ,

with E[ξ]=

and Var[ξ]=

Exponential: exp(

)

f (

−

λξ

, 0 ≤

> 0 ,

with E[ξ]=

and Var[ξ]=

Normal: N(

)

f (

√

πσ

−

(

−

)

> 0 ,

with E[ξ]=

and Var[ξ]=

Gamma: G(

)

f (

(

)

−1

−

> 0 ,

where

(



∞

−1

−x

dx ,

> 0, E[ξ]=

αβ

and Var[ξ]=

αβ

References

1. P.G. Abrahamson, “A Nested Decomposition Approach for Solving Staircase Linear Pro-

grams,” Ph.D. Dissertation, Stanford University (Stanford, CA, 1983).

2. D. Adelman, “Dynamic bid prices in revenue management,” Operations Research 55 (2007)

pp. 647–661.

3. S. Ahmed, “Convexity and decomposition of mean-risk stochastic programs,” Mathematical

Programming Series A 106 (2006) pp. 433–446.

4. S. Ahmed, M. Tawarmalani, and N. V. Sahinidis, “A ﬁnite branch and bound algorithm for

two-stage stochastic integer programs,” Mathematical Programming 100 (2004) pp.355-377.

5. E.D. Andersen, “ The homogeneous and self-dual model and algorithm for linear optimiza-

tion,” MOSEK Technical report: TR-1-2009, Copenhagen, DK, 2009.

6. S.A. Andreou, “A capital budgeting model for product-mix ﬂexibility,” Journal of Manufac-

turing and Operations Management 3 (1990) pp. 5–23.

7. K.M. Anstreicher, “A combined Phase I–Phase II projective algorithm for linear program-

ming,” Mathematical Programming 43 (1989) pp. 209–223.

8. K.A. Ariyawansa and D.D. Hudson, “Performance of a benchmark parallel implementa-

tion of the Van Slyke and Wets algorithm for two-stage stochastic programs on the Se-

quent/Balance,” Concurrency Practice and Experience 3 (1991) pp. 109–128.

9. P. Artzner, F. Delbaen, J-M. Eber and D. Heath, “Coherent measures of risk,” Mathematical

Finance 9 (1999) pp. 203-228.

10. R. Ashford, “Bounds and an approximate solution method for multistage stochastic produc-

tion problems,” Warwick Papers in Industry, Business and Administration, No. 15, University

of Warwick, Coventry, UK (1984).

11. S. Asmussen and P. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, New

York, 2007.

12. H. Attouch and R.J-B Wets, “Approximation and convergence in nonlinear optimization”

in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, Eds., Nonlinear programming, 4

(Academic Press, New York–London, 1981) pp. 367–394.

13. M. Avriel and A.C. Williams, “The value of information and stochastic programming,” Op-

erations Research 18 (1970) pp. 947–954.

14. O. Bahn, J.-L. Gofﬁn, O. du Merle, and J.-Ph. Vial, “A cutting plane method from analytic

centers for stochastic programming,” Mathematical Programming, 69 (1995) pp. 45–73.

15. G. Bayraksan and D.P. Morton, “A sequential sampling procedure for stochastic program-

ming,” Working Paper, University of Arizona, July, 2009.

16. M.S. Bazaraa and C.M. Shetty, Nonlinear Programming: Theory and Algorithms (John Wi-

ley, Inc., New York, NY, 1979).

17. M.S. Bazaraa, J.J. Jarvis, and H.D. Sherali, Linear Programming and Network Flows (John

Wiley, Inc., New York, NY, 1990).

451

452 References

18. E.M.L. Beale, “On minimizing a convex function subject to linear inequalities,” J. Royal

Statistical Society, Series B 17 (1955) pp. 173–184.

19. E.M.L. Beale, “The use of quadratic programming in stochastic linear programming,” Rand

Report P-2404-1, The Rand Corporation (1961).

20. E.M.L. Beale, J.J.H. Forrest, and C.J. Taylor, “Multi-time-period stochastic programming”

in: M.A.H. Dempster, Ed., Stochastic Programming (Academic Press, New York, NY, 1980)

pp. 387–402.

21. E.M.L. Beale, G.B. Dantzig, and R.D. Watson, “A ﬁrst order approach to a class of

multi-time-period stochastic programming problems,” Mathematical Programming Study 27

(1986) pp. 103–117.

22. R. Bellman, Dynamic Programming (Princeton University Press, Princeton, NJ, 1957).

23. Ben-Tal, A., Boyd, S., Nemirovski, A., Extending the Scope of Robust Optimization: Com-

prehensive Robust Counterparts of Uncertain Problems, Mathematical Programming 107:1-2

(2006), 63–89.

24. Ben-Tal, A. and Arkadi Nemirovski, A. (2002). Robust optimizationmethodology and appli-

cations, Mathematical Programming, Series B 92, 453–480.

25. A. Ben-Tal and M. Teboulle, “Expected utility, penalty functions, and duality in stochastic

nonlinear programming,” Management Science 32 (1986) pp. 1445–1466.

26. J. F. Benders, “Partitioning procedures for solving mixed-variables programming problems,”

Numerische Mathematik 4 (1962) pp. 238–252.

27. B. Bereanu, “Some numerical methods in stochastic linear programming under risk and un-

certainty” in: M.A.H. Dempster, Ed., Stochastic Programming (Academic Press, New York,

NY, 1980) pp. 169–205.

28. J.O. Berger, Statistical Decision Theory and Bayesian Analysis (Springer-Verlag, New York,

NY, 1985).

29. O. Berman, R.C. Larson, and S.S. Chiu, “Optimal server location on a network operating as

a M/G/1 queue,” Operations Research 33 (1985) pp. 746–770.

30. D.P. Bertsekas, Dynamic Programming and Optimal Control, Volume II, Third Edition

(Athena Scientiﬁc, Boston, 2007).

31. D.P. Bertsekas and J.N. Tsitsiklis, Neuro-Dynamic Programming (Athena Scientiﬁc, Boston,

1995).

32. D. Bertsimas, D.A. Iancu, and P.A. Parrilo, “Optimality of afﬁne policies in multistage robust

optimization,” Mathematics of Operations Research 35 (2010) pp. 363–394.

33. D. Bertsimas, P. Jaillet, and A. Odoni, “A priori optimization,” Operations Research 38

(1990) pp. 1019–1033.

34. D. Bertsimas, K. Natarajan, and C-P. Teo, “Probabilistic combinatorial optimization: Mo-

ments, semideﬁnite programming and asymptotic bounds,” SIAM J. of Optimization 15

(2004) pp. 185-209.

35. D. Bertsimas and I. Popescu, “ Optimal inequalities in probability: A convex programming

approach,” SIAM Journal of Optimization, 15 (2004) pp. 780–804.

36. D. Bertsimas and M. Sim, “Tractable approximations to robust conic optimization problems,”

Mathematical Programming 107 (2006) pp. 5–36.

37. D. Bienstock and J.F. Shapiro, “Optimizing resource acquisition decisions by stochastic pro-

gramming,” Management Science 34 (1988) pp. 215–229.

38. P. Billingsley, Convergence of Probability Measures (John Wiley, Inc., New York, NY, 1968).

39. J.R. Birge, “Solution Methods for Stochastic Dynamic Linear Programs,” Ph.D. Dissertation

and Technical Report SOL 80-29, Systems Optimization Laboratory, Stanford University

(Stanford, CA, 1980).

40. J.R. Birge, “The value of the stochastic solution in stochastic linear programs with ﬁxed

recourse,” Mathematical Programming 24 (1982) pp. 314–325.

41. J.R. Birge, “Using sequential approximations in the L-shaped and generalized programming

algorithms for stochastic linear programs,” Technical Report 83-12, Department of Industrial

and Operations Engineering, University of Michigan (Ann Arbor, MI, 1983); available at

http://hdl.handle.net/2027.42/3642.

References 453

42. J.R. Birge, “Aggregation in stochastic production problems,” Proceedings of the 11th IFIP

Conference on System Modelling and Optimization (Springer-Verlag, New York, 1984).

43. J.R. Birge, “Aggregation in stochastic linear programming,” Mathematical Programming 31

(1985a) pp. 25–41.

44. J.R. Birge, “Decomposition and partitioning methods for multi–stage stochastic linear pro-

grams,” Operations Research 33 (1985b) pp. 989–1007.

45. J.R. Birge, “Exhaustible recourse models with uncertain returns from exploration invest-

ment” in: Y. Ermoliev and R. Wets, Eds., Numerical Techniques for Stochastic Optimization

(Springer-Verlag, Berlin, 1988a) pp. 481–488.

46. J.R. Birge, “The relationship between the L-shaped method and dual basis factorization for

stochastic linear programming” in: Y. Ermoliev and R. Wets, Eds., Numerical Techniques for

Stochastic Optimization (Springer-Verlag, Berlin, 1988b) pp. 267–272.

47. J.R. Birge, “Multistage stochastic planning models using piecewise linear response func-

tions” in: G. Dantzig and P. Glynn, Eds., Resource Planning under Uncertainty for Electric

Power Systems (NSF, 1989).

48. J.R. Birge, “Quasi-Monte Carlo methods for option evaluation,” Technical Report, Depart-

ment of Industrial and Operations Engineering , University of Michigan (Ann Arbor, MI,

1994); available at http://hdl.handle.net/2027.42/3632.

49. J.R. Birge, “Option methods for incorporating risk into linear capacity planning models,”

Manufacturing and Service Operations Management 2 (2000), pp. 189–194.

50. J.R. Birge and M.A.H. Dempster, “Optimality conditions for match-up strategies in stochas-

tic scheduling and related dynamic stochastic optimization problems,” Technical Report 92-

58, Department of Industrial and Operations Engineering, University of Michigan (Ann Ar-

bor, MI, 1992); available at http://hdl.handle.net/2027.42/3645.

51. J.R. Birge, C.J. Donohue, D.F. Holmes, and O.G. Svintsiski, “A parallel implementation of

the nested decomposition algorithm for multistage stochastic linear programs,” Mathematical

Programming 75 (1996) pp. 327–352.

52. J.R. Birge and J. Dul´a, “Bounding separable recourse functions with limited distribution

information,” Annals of Operations Research 30 (1991) pp. 277–298.

53. J.R. Birge, R.M. Freund, and R.J. Vanderbei, “Prior reduced ﬁll-in in the solution of equa-

tions in interior point algorithms,” Operations Research Letters 11 (1992) pp. 195–198.

54. J.R. Birge and D.F. Holmes, “Efﬁcient solution of two-stage stochastic linear programs using

interior point methods,” Computational Optimization and Applications 1 (1992) pp. 245–

276.

55. J.R. Birge and F.V. Louveaux, “A multicut algorithm for two-stage stochastic linear pro-

grams,” European Journal of Operations Research 34 (1988) pp. 384–392.

56. J.R. Birge and M.J. Maddox, “Bounds on expected project tardiness,” Operations Research

43 (1995) pp. 838–850.

57. J.R. Birge and M.J. Maddox, “Using second moment information in stochastic scheduling”

in: G. Yin and Q. Zhang, Eds., Recent Advances in Control and Manufacturing Systems

(Springer-Verlag, New York, NY, 1996) pp. 99–120.

58. J.R. Birge and L. Qi, “Computing block-angular Karmarkar projections with applications to

stochastic programming,” Management Science 34 (1988) pp. 1472–1479.

59. J.R. Birge and L. Qi, “Semiregularity and generalized subdifferentials with applications to

optimization,” Mathematics of Operations Research 18 (1993) pp. 982–1006.

60. J.R. Birge and L. Qi, “Subdifferential convergence in stochastic programs,” SIAM J. Opti-

mization 5 (1995) pp. 436–453.

61. J.R. Birge and C.H. Rosa, “Parallel decomposition of large-scale stochastic nonlinear pro-

grams,” Annals of Operations Research 64 (1996), pp. 39–65.

62. J.R. Birge and M. Teboulle, “Upper bounds on the expected value of a convex function using

subgradient and conjugate function information,” Mathematics of Operations Research 14

(1989) pp. 745–759.

63. J.R. Birge and S.W. Wallace, “Reﬁning bounds for stochastic linear programs with linearly

transformed independent random variables,” Operations Research Letters 5 (1986) pp. 73–

77.