9512.net
甜梦文库
当前位置:首页 >> 电力/水利 >>

A note on scenario reduction for two-stage stochastic programs两阶段随机规划注意减少场景


Operations Research Letters 35 (2007) 731 – 738

Operations Research Letters
www.elsevier.com/locate/orl

A note on scenario reduction for two-stage stochastic programs
Holger Heitsch, Werner R?misch?
Institute of Mathematics, Humboldt-University Berlin, 10099 Berlin, Germany Received 30 May 2006; accepted 7 December 2006 Available online 11 January 2007

Abstract We extend earlier work on scenario reduction by relying directly on Fortet–Mourier metrics instead of using upper bounds given in terms of mass transportation problems. The importance of Fortet–Mourier metrics for quantitative stability of twostage models is reviewed and some numerical results are also provided. ? 2007 Elsevier B.V. All rights reserved.
Keywords: Stochastic programming; Mass transportation; Probability metric; Two-stage; Scenario reduction

1. Introduction In the papers [2,5] a stability-based methodology is developed for reducing the set of scenarios in convex stochastic programming models. Such a reduction may be desirable in some situations when the underlying optimization models already happen to be large scale and the incorporation of a large number of scenarios might lead to huge programs and, hence, to high computation times. The idea of the scenario reduction framework in [2,5] is to compute the (nearly) best approximation of the underlying discrete probability distribution by a measure with smaller support in terms of a probability metric which is associated to the stochastic program in a natural way. Such “natural” (or canonical) metrics for probability measures are known

? Corresponding author.

E-mail address: romisch@math.hu-berlin.de (W. R?misch). 0167-6377/$ - see front matter ? 2007 Elsevier B.V. All rights reserved. doi:10.1016/j.orl.2006.12.008

for (linear) two-stage stochastic programs: the rth order Fortet–Mourier metrics, where the choice of r 1 depends on the speci?c structure of the programs (see Section 3 and [10,11]). However, the strategies for scenario reduction developed in [2,5] are not based on Fortet–Mourier metrics, but on their upper bounds in form of certain mass transportation problems which enjoy speci?c properties and representations. In the present note we remove this drawback and develop scenario reduction algorithms that are rigorously based on Fortet–Mourier metrics. The key step in this direction is that we do no longer use the (generalized) distances c for scenarios as in [2,5], but so-called reduced distances (or costs) c ? which, indeed, are distances in the ?nite-dimensional scenario space and represent in?ma of certain optimization problems. Our paper is organized as follows. In Section 2 we discuss distances of (multivariate) probability measures that are based on mass transportation problems.

732

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

We review some of their topological properties, duality results and representations that are needed in the sequel. Section 3 reviews stability properties of multiperiod two-stage stochastic programs with respect to the distances introduced in the previous section. In Section 4 we extend our earlier theory and heuristic algorithms for optimal scenario reduction to the relevant metrics. Finally, we present some numerical experience for the new forward algorithm of scenario reduction. It is tested on realistic data from electricity portfolio management.

If P and Q are discrete probability measures having ?nitely many scenarios i (with probabilities pi ), i = 1, . . . , N , and ? j =: N +j (with probabilities qj ), j = 1, . . . , M , respectively, we obtain ? ?N M ? ? c (P , Q) = inf ij c( i , j ) : ij 0, ? i =1 j =1 ? N M ? , = q = p , i j ij ij ?
j =1 i =1

2. Distances of probability distributions A variety of distances of multivariate probability distributions are related to mass transportation problems. If P and Q belong to the set P( ) of all (Borel) probability measures on a closed subset of Rs and c : × → R is a nonnegative, symmetric and continuous cost function for transporting P to Q, the minimal transportation cost is given by ? c (P , Q) := inf
×

i.e. ? c (P , Q) is the optimal value of a linear transportation problem, and ? ?N +M ? c( i , j ) ij : ij 0, c (P , Q) = inf ? i,j =1 ? N +M N +M ? ? = P ( { } ) ? Q( { } ) , i i ij ji ?
j =1 j =1

c( , ? ) (d , d ? ) :
1

∈ P( × ),

= P,

2

=Q ,

(1)

i.e. c (P , Q) is the optimal value of a minimum cost ?ow problem. Hence, for discrete probability measures with ?nite support both functionals are computationally accessible. The most important cost functions in the context of the present paper are cr ( , ? ) := max{1, · ?? ? 0 r ?1 , ? ? ( , ? ∈ ),
0 r ?1

?

where 1 and 2 denote the projections onto the ?rst and second components, respectively. A minimizer ? ∈ P( × ) of (1) is called optimal transportation plan and ? c de?ned on P( ) × P( ) is a so-called Monge–Kantorovich functional. A variant of (1) is the mass transshipment problem given by
? c (P , Q)

} (3)

for some r 1 and 0 ∈ . In this case, both func? tionals ? c (P , Q) and c (P , Q) are ?nite if P and Q belong to the set Pr ( ) of all probability measures having absolute moments of order r. We will use the ? ? notation ? r and r for ? cr and cr , respectively. The Kantorovich–Rubinstein functional r is a metric on Pr ( ), called the Fortet–Mourier metric of order r [3]. It satis?es the estimate
r ?

:= inf

×

c( , ? ) (d , d ? ) :
1

∈ M( × ),

?

2

=P ?Q ,

(2)

where M( × ) denotes the set of all ?nite measures ? on × and c de?ned on P( ) × P( ) is called Kantorovich–Rubinstein functional. We refer to [7,9] for a comprehensive presentation of theory and applications of mass transportation problems.

P (d ) ?

r

Q(d )

r

?

r (P , Q)

(4)

for all P , Q ∈ Pr ( ) [7, Theorem 6.2.5]. Moreover, convergence of a sequence (Pn ) of probability mea? sures in the metric space (Pr ( ), r ) to some limit P

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

733

is equivalent to ( ? r (Pn , P )) tending to 0 as n → ∞ and to the weak convergence of (Pn ) to P and the convergence of rth order absolute moments of Pn to those of P [7, Theorems 6.3.1]. The following dual representation and characterization are of special interest here. The corresponding results are derived in [7, Theorem 5.3.2] and [9, Section 4.3]. Proposition 2.1. For all probability measures P , Q ∈ ? Pr ( ) the Kantorovich–Rubinstein functional r admits the dual representation
? r (P , Q) =

3. A review of stability for two-stage models If the second stage of a linear stochastic program with recourse models a (stochastic) dynamical decision process, as is the case in a variety of applications, the two-stage problem takes on the form min f0 ( , x)P (d ) : x ∈ X , (8)

a closed where X is a polyhedral subset of Rm , subset of Rs , P is a Borel probability measure on and the integrand f0 is of the form f0 ( , x) = c, x + inf ? ? ?
j =1

f ∈Fr

sup

f ( )P (d ) ?

f ( )Q(d ) , (5)

qj ( ), yj :

where Fr is the class of functions f : → R satisfying f ( ) ? f ( ? ) cr ( , ? ), ? , ? ∈ . Proposition 2.2. Let be compact and r 1. Then the Kantorovich–Rubinstein functional with cost function cr coincides with a Monge–Kantorovich functional with reduced cost c ?r . More precisely, it holds
? r (P , Q) = ? c ?r (P , Q) =

Wj yj = hj ( ) ? Tj ( )yj ?1 , ? ? yj ∈ Yj , j = 1, . . . , , ?

(9)

?c ?r (P , Q)

? r (P , Q), (6) × is given by

where the real-valued function c ?r on c ?r ( , ? ) := inf
n?1

cr ( i ,
i =1

i +1 )

: n ∈ N, (7) cr and

i

∈ ,

1

= ,

n

=? . with c ?r

The function c ?r is a metric on coincides with cr if r = 1.

The compactness assumption in Proposition 2.2 is not restrictive here since it will be used for probability measures with ?nite support. The importance of Proposition 2.2 in the present context is due to the fact that Kantorovich–Rubinstein functionals are appropriate for stability issues (see Section 3), but Monge–Kantorovich functionals, i.e., mass transportation problems, allow for special representations (see Section 4).

with c ∈ Rm , polyhedral subsets Yj of Rmj , recourse costs qj ( ) ∈ Rmj , right-hand sides hj ( ) ∈ Rrj , technology matrices Tj ( ) ∈ Rrj ×mj ?1 and recourse matrices Wj ∈ Rrj ×mj for j = 1, . . . , and some ∈ N; the vectors qj (·), hj (·) and the matrices Tj (·) are (potentially) stochastic and af?ne functions of . Then the second stage program has separable block structure and the recourse variable y has the form y = (y1 , . . . , y ). When rewriting the model as a two-stage stochastic programming model with recourse decision y = (y1 , . . . , y ), the recourse matrix has separable block structure with W1 , . . . , W and the matrices T1 ( ), . . . , T ( ) appearing as its main and lower diagonal blocks. The following stability result for optimal values v(P ) and -approximate ?rst-stage solution sets S (P ) of (8), (9) is derived in the recent paper [11]. Proposition 3.1. Let P ∈ P +1 ( ) and the solution set S(P ) of (8), (9) be nonempty and bounded. Assume that hj ( ) ? Tj ( )x ∈ Wj (Yj ) holds for each j = 1, . . . , and all pairs ( , x) ∈ × X (relatively complete recourse). Moreover, assume ker (Wj )∩Yj∞ ={0} for j = 1, . . . , ? 1, where Yj∞ denotes the (polyhedral) horizon cone to Yj .

734

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

Then there exist constants L > 0 and ? > 0 such that for any ∈ (0, ?) the estimates |v(P ) ? v(Q)| L d∞ (S (P ), S (Q))
? +1 (P , Q), L? +1 (P , Q), ?

hold whenever Q ∈ P +1 ( ) and +1 (P , Q) < . Here, d∞ denotes the Pompeiu–Hausdorff distance on compact subsets of Rm . We note that the horizon cone Yj∞ contains all elements xj ∈ Rmj such that x + xj ∈ Yj for all x ∈ Yj and ∈ R+ . The condition ker (Wj ) ∩ Yj∞ = {0} implies the boundedness of the constraint set {yj ∈ Yj : Wj yj = uj } for all right-hand sides uj . The case = 1 corresponds to the situation of linear two-stage models with ?xed recourse (see [10, Theorem 24]). Hence, together with the results in [8,10], the number r should be selected as r = 1 if either costs or right-hand sides in (8), (9) are random, r = 2 if only costs and right-hand sides are random in (8), (9) and r = + 1 if, in addition, all technology matrices are random in (8) and (9). Since the (approximate) optimal second stage decisions are compact with respect to the weak topology in some space Lr ( , F, P; Rm ) with m = j =1 mj , some probability space ( , F, P) and some r related to r [6], a choice of r larger than suggested may lead to stronger properties of the second stage decisions. 4. Optimal scenario reduction Let P be a discrete probability distribution with scenarios i and probabilities pi , i = 1, . . . , n. If the number n of scenarios is large, one might wish to delete scenarios of P in a best possible way, i.e., such that the original problem or, more precisely, its optimal value admits minimal changes. To make this requirement precise, we denote by QJ a discrete distribution whose support consists of a subset of scenarios j , j ∈ {1, . . . , n}\J , of P having probabilities qj , j∈ / J . Hence, it is of interest to determine a subset J of {1, . . . , n} and probabilities qj , j ∈ / J , such that the distance |v(P ) ? v(QJ )| of optimal values is minimal with respect to all subsets of given cardinality. But, in general, this distance is dif?cult to handle. According to Proposition 3.1 we know, however, that, for

two-stage models, |v(P ) ? v(QJ )| can be estimated by a multiple of some metric or functional of P and QJ . Hence, one might consider (P , QJ ) instead and arrives at the principle of optimal scenario reduction: Fix k ∈ N, k < n, and determine a solution of the minimization problem ? ? min (P , QJ ) : J ? {1, . . . , n}, ? ? ? qj = 1 . (10) #J = n ? k, qj 0, ?
j∈ /J

In a ?rst step, it is of interest to ?x J and to determine the optimal weights qj , j ∈ / J , such that QJ is a probability measure, i.e., to solve the best approximation problem. ? ? ? ? min (P , QJ ) : qj 0, qj = 1 . (11) ? ?
j∈ /J

The next result asserts that the latter problem (11) is solvable and provides an explicit representation of the ? in?mum in case = r . Theorem 4.1. For given nonempty subset J of {1, . . . , n} problem (11) has a solution Q? J = ? q and it holds j∈ /J j j DJ :=
?

, Q? r (P? J) ?? ?
r (P , QJ )

= min =
i ∈J

: qj
j)

0,
j∈ /J

qj = 1

? ? ?

pi min c ?r ( i ,
j∈ /J m?1

=
i ∈J

pi min
=1

cr (

l

,

l

+1

) : m ∈ N, (12)

l ∈ {1, . . . , n}, l1 = i, lm = j ∈ /J ,

? = p + where qj / J , with Jj := j i ∈Jj pi , ?j ∈ {i ∈ J |j = j (i)} and the index j (i) belonging to arg minj ∈ ?r ( i , j ), ?i ∈ J , i.e., the optimal re/J c distribution consists in adding each deleted scenario

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

735

8000 7000 6000 5000 4000 3000 0 24 48 72 96 120 144 168

1000

500

0

-500

-1000 0 24 48 72 96 120 144 168

Fig. 1. Load scenarios for one week and mean shifted initial load scenario tree.

weight to that of some of those scenarios being closest w.r.t. c ?. Proof. Due to Proposition 2.2 we have the identity ? r (P , QJ )= ? c ?r (P , QJ ), where the reduced cost function c ?r is a metric on the support of P. Since [2, Theorem 2] is established for the Monge–Kantorovich functional, it implies the desired representation ? ? ? ? (P , Q ) : q 0 , q = 1 min ? c J j j ? ? ?r
j∈ /J

approximation algorithms for the metric k-median problem in [1] and [12, Chapter 25] achieve guarantees of 6 2 3 and 6 times the optimal. Simple heuristics may be derived by extending the two extremal cases k = n ? 1 and k = 1 of problem (13). These problems correspond to solving
l ∈{1,...,n}

min

pl min c ?r ( l ,
j =l

j)

(k = n ? 1)

and
n u∈{1,...,n}

min

=
i ∈J

pi min c ?r ( i ,
j∈ /J

j ),

pi c ?r ( u , i )
i =1 i =u

(k = 1).

together with the asserted redistribution rule. The preceding result coincides with [2, Theorem 2] if cr is a metric, i.e., r = 1. Using the explicit formula (12), the problem (10) of optimal scenario reduction is of the form min DJ =
i ∈J

pi min c ?r ( i ,
j∈ /J

j)

: (13)

Their solutions are the index sets J = {l1 } and {1, . . . , n}\{u1 }, respectively. The two sets arise from different algorithmic ideas: backward reduction and forward selection. Both ideas can be extended and lead to backward and forward heuristics for ?nding approximate solutions of (13). For example, the forward selection procedure determines an index set J [k ] of deleted scenarios having cardinality n ? k . Algorithm 4.2 (Forward selection). Step[0] : Step[i] : J [0] := {1, . . . , n}. ui ∈ arg min pk

J ? {1, . . . , n}, #J = n ? k ,

i.e., it represents a metric k-median problem in the metric space ( , c ?r ). The problem is known to be NP-hard, hence, (polynomial-time) approximation algorithms and heuristics become important. The

Step[k + 1] : Optimal redistribution.

min c ?r ( k , j ), j∈ / J [i ?1] \{u} [ i ] [ i ? 1 ] J := J \{ui }.

u∈J [i ?1] k ∈J [i ?1] \{u}

736

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

This algorithm was ?rst studied in [5] for the case c ?r = cr . There it is shown that the algorithm requires O(k n2 ) operations. Although the algorithm does not lead to optimality in general, the performance evaluation of its implementation in [5] is very encouraging.

5. Numerical experience We consider the scenario tree in [2,5] representing the increasing uncertainty of electrical load in a stochastic electrical power production model for a
Table 1 Numerical results for optimal scenario reduction based on
Number of scenarios Relative r =1 1 5 10 20 50 100 150 200 300 400 500 600 1.000 0.522 0.419 0.323 0.230 0.169 0.137 0.117 0.094 0.072 0.050 0.028
? r -distances

weekly time horizon (see [4] for further information). The scenario tree is obtained by calibrating a time series model for the electrical load, by simulating a large number of load realizations, and by constructing an initial ternary load scenario tree based on sample means and standard deviations of the simulated realizations. The initial load scenario tree represents a discrete probability distribution P that consists of 36 = 729 uniformly distributed scenarios and enters a 7-period two-stage stochastic programming model (Fig. 1). Table 1 presents our computational results for optimal scenario reduction of the initial load

?

r

r =2 1.000 0.646 0.536 0.420 0.305 0.220 0.178 0.148 0.102 0.067 0.039 0.018

r =3 1.000 0.684 0.589 0.469 0.335 0.242 0.185 0.143 0.085 0.049 0.024 0.009

r =4 1.000 0.696 0.577 0.472 0.337 0.222 0.156 0.112 0.057 0.028 0.012 0.004

r =5 1.000 0.687 0.582 0.466 0.301 0.180 0.114 0.076 0.032 0.013 0.005 0.001

r =6 1.000 0.682 0.556 0.431 0.256 0.133 0.077 0.045 0.016 0.006 0.002 0.000

r =7 1.000 0.668 0.535 0.395 0.210 0.094 0.049 0.025 0.008 0.002 0.001 0.000

Table 2 Numerical results for optimal scenario reduction based on ? r
Number of scenarios Relative ? r -distances r =1 1 5 10 20 50 100 150 200 300 400 500 600 1.000 0.522 0.419 0.323 0.230 0.169 0.137 0.117 0.094 0.072 0.050 0.028 r =2 1.609 0.738 0.574 0.448 0.308 0.221 0.179 0.149 0.102 0.067 0.039 0.018 r =3 2.354 0.940 0.713 0.538 0.359 0.253 0.192 0.147 0.088 0.050 0.025 0.009 r =4 3.146 1.079 0.787 0.600 0.378 0.248 0.171 0.121 0.062 0.030 0.012 0.004 r =5 3.910 1.209 0.820 0.617 0.369 0.211 0.134 0.088 0.037 0.015 0.005 0.001 r =6 4.627 1.217 0.803 0.601 0.331 0.168 0.097 0.058 0.021 0.007 0.002 0.000 r =7 5.302 1.257 0.794 0.565 0.286 0.130 0.066 0.035 0.011 0.003 0.001 0.000

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

737

500

500

0

0

-500

-500

0

24

48

72

96

120

144

168

0

24

48

72

96

120

144

168

500

500

0

0

-500

-500

0 1000 500 0 -500 -1000 0 1000 500 0 -500 -1000 0

24

48

72

96

120

144

168 1000 500 0 -500 -1000

0

24

48

72

96

120

144

168

24

48

72

96

120

144

168 1000 500 0 -500 -1000

0

24

48

72

96

120

144

168

24

48

72

96

120

144

168
?

0

24

48

72

96

120

144

168

Fig. 2. Reduced trees containing k = 20 scenarios obtained by using r (left column) and ? r (right column) for r = 1, 2, 4, 7.

738

H. Heitsch, W. R?misch / Operations Research Letters 35 (2007) 731 – 738

scenario tree by using Algorithm 4.2. A comparison ? with Table 2 shows the improvement of using r instead of ? r . Both tables display the relative distances between the original load tree and some of the reduced ones, and the effects of varying the order r ? of the Fortet–Mourier metrics r and the functionals ? r , respectively. The relative distances are computed by dividing all distances by the Fortet–Mourier distance between the initial load distribution P and the Dirac measure at the scenario obtained in the ?rst for? ward selection step, i.e., by r (P , u ). To compute 1 a reduced tree for r = 1, the running time on a PC equipped with a 3 GHz processor is less than 10 s including about 4 s to compute the scenario distances cr (·, ·). For r > 1about 9 s are needed in addition to compute the reduced cost c ?r (·, ·). Fig. 2 illustrate the structure of the reduced scenario trees consisting of 20 scenarios for varying order r. As approximations ? of probability distributions with respect to r approximately recover rth order absolute moments (see (4)), different scenarios for different r are selected with a tendency to outer scenarios for growing r. Acknowledgements This work was supported by the DFG Research Center MATHEON “Mathematics for key technologies” in Berlin, the BMBF and a grant of EDF—Electricité de France. The authors wish to thank the referee for his suggestions to improve the presentation and A. Martin (University of Darmstadt) and J. Rambau (University of Bayreuth) for helpful discussions.

References
[1] M. Charikar, S. Guha, E. Tardos, D.B. Shmoys, A constantfactor approximation algorithm for the k-median problem, J. Comput. Syst. Sci. 65 (2002) 129–149. [2] J. Dupaˇ cová, N. Gr?we-Kuska, W. R?misch, Scenario reduction in stochastic programming: an approach using probability metrics, Math. Program. 95 (2003) 493–511. [3] R. Fortet, E. Mourier, Convergence de la répartition empirique vers la répartition théorique, Ann. Sci. Ecole Norm. Sup. 70 (1953) 266–285. [4] N. Gr?we-Kuska, W. R?misch, Stochastic unit commitment in hydro-thermal power production planning, in: S.W. Wallace, W.T. Ziemba (Eds.), Applications of Stochastic Programming, MPS-SIAM Series in Optimization, 2005, pp. 633–653. [5] H. Heitsch, W. R?misch, Scenario reduction algorithms in stochastic programming, Comput. Optim. Appl. 24 (2003) 187–206. [6] H. Heitsch, W. R?misch, C. Strugarek, Stability of multistage stochastic programs, SIAM J. Optim. 17 (2006) 511–525. [7] S.T. Rachev, Probability Metrics and the Stability of Stochastic Models, Wiley, New York, 1991. [8] S.T. Rachev, W. R?misch, Quantitative stability in stochastic programming: the method of probability metrics, Math. Oper. Res. 27 (2002) 792–818. [9] S.T. Rachev, L. Rüschendorf, Mass Transportation Problems, vols. I and II, Springer, Berlin, 1998. [10] W. R?misch, Stability of stochastic programming problems, in: A. Ruszczy? nski, A. Shapiro (Eds.), Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10, Elsevier, Amsterdam, 2003, pp. 483–554. [11] W. R?misch, R.J.-B. Wets, Stability of -approximate solutions to convex stochastic programs, preprint 325, DFG Research Center Matheon “Mathematics for key technologies”, SIAM J. Optim. (2006), submitted. [12] V.V. Vazirani, Approximation Algorithms, Springer, Berlin, 2001.


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图