risk balanced management of scarce resources using stochastic programming

risk balanced management of scarce resources using stochastic programming

European Journal of Operational Research 216 (2012) 214–224 Contents lists available at ScienceDirect European Journal of Operational Research journ...

785KB Sizes 3 Downloads 48 Views

European Journal of Operational Research 216 (2012) 214–224

Contents lists available at ScienceDirect

European Journal of Operational Research journal homepage: www.elsevier.com/locate/ejor

Innovative Applications of O.R.

Cost/risk balanced management of scarce resources using stochastic programming Alexei Gaivoronski a,⇑, Giovanni M. Sechi b, Paola Zuddas b a b

Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway Department of Land Engineering, University of Cagliari, Italy

a r t i c l e

i n f o

Article history: Received 23 April 2010 Accepted 29 June 2011 Available online 8 July 2011 Keywords: OR in natural resources Risk management Stochastic programming Water resources management Risk/performance tradeoff

a b s t r a c t We consider the situation when a scarce renewable resource should be periodically distributed between different users by a Resource Management Authority (RMA). The replenishment of this resource as well as users demand is subject to considerable uncertainty. We develop cost optimization and risk management models that can assist the RMA in its decision about striking the balance between the level of target delivery to the users and the level of risk that this delivery will not be met. These models are based on utilization and further development of the general methodology of stochastic programming for scenario optimization, taking into account appropriate risk management approaches. By a scenario optimization model we obtain a target barycentric value with respect to selected decision variables. A successive reoptimization of deterministic model for the worst case scenarios allows the reduction of the risk of negative consequences derived from unmet resources demand. Our reference case study is the distribution of scarce water resources. We show results of some numerical experiments in real physical systems. Ó 2011 Elsevier B.V. All rights reserved.

1. Introduction In this paper we deal with quantitative planning and management models for distribution of scarce resources under uncertainty and conflicting demands of different users and activities. A recurring reference which we make is a distribution system of water resources in a region where such resources are scarce; see for example Loucks et al. (1981), Dembo (1995) and Sechi et al. (2005). However, the methods which we consider here are applicable to a wide range of management problems in other, different areas, like distribution of manpower in a call center, distribution of transportation or transmission capacities, assignment of empty containers, etc. We address the case when the planning horizon extends for a substantial amount of time periods. These periods are connected with each other by the flow balance equations which connect the amount of the resource inherited from the previous period with the amount of resource which will be available in the next period, taking into account consumption and replenishment of the resource at the current time period. This relation makes the future state of the system dependent on the current decision about the resource expenditure. Consequently, it is necessary to foresee the future replenishment and consumption of the resource in order to make the optimal management decision now. There is substantial uncertainty about these forecasts, especially about replenishment process. Indeed, in the case of water resources it is necessary to ⇑ Corresponding author. Tel.: +47 48243742. E-mail addresses: [email protected] (A. Gaivoronski), [email protected] it (G.M. Sechi), [email protected] (P. Zuddas). 0377-2217/$ - see front matter Ó 2011 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2011.06.040

predict the highly changing and uncertain water inflow patterns for the time in consideration, and such forecasts are inherently very imprecise. Additional sources of uncertainty come from projections of future demand, costs and prices. An adequate management policy cannot be defined without adequate consideration of this uncertainty; therefore deterministic mathematical programming models are of limited use here. One way to address this problem is to construct a set of scenarios about the future values of uncertain parameters, like the values of replenishment and demand processes for each future time period. Then scenario analysis is employed in order to construct the optimal decision policies for each scenario and to investigate the sensitivity of these decisions with respect to the changes in uncertain parameters. This can be a useful technique, especially when the scenarios do not differ drastically between each other. In such a situation it may be possible to identify a decision policy that will be relatively stable with respect to scenarios. However, in the problems which we address here this is not the case because different replenishment scenarios can differ substantially between themselves. In such circumstances an optimal policy for one scenario may have little in common with the optimal or even acceptable policy for some other scenario. These difficulties can be overcome by using the stochastic programming approach (Ermoliev and Wets, 1988; Kall and Wallace, 1994; Pflug, 1996; Birge and Louveaux, 1997 and Kleywegt and Shapiro, 2001); for application to water resources management see Dupacová et al. (1991), Pallottino et al. (2004) and Escudero and Monge (2008). One way to utilize this methodology is to describe the uncertainty by organizing scenarios in scenario trees. A probability

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

215

is assigned to each scenario. These probabilities can be recovered from statistical processing of historical data, but they can be also assigned subjectively by experts. The objective function of stochastic programming problem is defined by weighting the costs or profits associated with each scenario with these probabilities. The structure of scenario tree allows formulating a deterministic equivalent of multistage stochastic programming problem by collecting all constraints that define the feasibility sets for each scenario and adding nonanticipativity constraints, which assure that the decision variables associated with different scenarios, will be the same until the time period where scenarios start to differ. Besides references mentioned above, detailed description of different aspects of such multistage stochastic programs with uncertainty described by scenario trees can be found in Rockafellar and Wets (1991), Higle and Sen (1996), Ruszczynski (1997), Lucas et al. (2001) and Römisch and Schultz (2001). Application examples to investment planning are given in Mulvey and Vladimirou (1991), Cariño and Ziemba (1998), Consigli and Dempster (1998) and Zenios (2008), to air traffic management in Glockner and Nemhauser (2000), to insurance in Gaivoronski and de Lange (2000) and Høyland and Wallace (2001), to telecommunications planning in Gaivoronski (2006), to electric power planning in Fleten and Kristoffersen (2006), to facility location in Stougie et al. (2008), to empty containers allocation in Di Francesco et al. (2009), see also Wallace and Ziemba (2005) for representative collection of applied problems. Detailed application of stochastic programming approach to water resource management was considered in Pallottino et al. (2004) and Manca et al. (2004), where following Rockafellar and Wets (1991) it is also referred to as scenario optimization. The specifics of this application field have not allowed the use of statistical techniques for scenario generation due to considerable climate non-stationarities verified during last years. Therefore scenario generation was based upon expert knowledge, hence the term Subjective Stochastic approach, introduced there. Our reference application field in this paper is planning and management of water resources. This field has attracted considerable attention of international research community. Recent examples and comparisons of deterministic multicriteria planning models are presented in Mariano-Romero et al. (2007) and Hajkowicz and Higgins (2008). Different methods of incorporating uncertainty into water resources planning models were also a subject of recent research. In addition to already cited Dupacová et al. (1991) and other papers where stochastic programming approach was considered, one can mention Huang (1998) who developed a single period model with hybrid stochastic and interval representation of uncertainty. This work was extended to the case of two periods by Maqsood et al. (2005). A single period nonlinear stochastic optimization model with stochastic inflows and water deficit was developed by Azaiez and Hariga (2001). A single period goal programming formulation under uncertainty that balances between the needs to satisfy agricultural demand and limit the environmental impact was considered by Bravo and Gonzalez (2009). Weng et al. (2010) develop multicriteria model for scenario analysis that is capable of incorporating uncertainty. Our paper distinguishes itself from this literature by incorporating risk management approach into multistage stochastic optimization model for water resources management with the uncertainty being described by scenario trees. More specifically, it presents the following novel contributions.

should find a distribution pattern which will in the best possible way satisfy conflicting needs of different users and overall system performance criterion in the situation when the combined requirements exceed the system capacity. The overall management policy in such situation will consist of two components.

1.1. Target resource delivery policy

2. Multiperiod stochastic programming model for water resource management under uncertainty

This is a modeling solution which responds to the specifics of distribution of scarce resource. Often such distribution is performed by a Resource Management Authority (RMA) responsible for functioning of the storage and distribution system. This authority

1. The RMA makes decision about the target resource delivery to the users. This target delivery is communicated to the users together with the (usually high) level of reliability of this delivery. This phase is performed by a cost/risk balanced model calibrated with intensive use of simulation tools. 2. After receiving this information about the target delivery the users develop their own resource management policy that takes into account a possible shortfall between the target delivery and their needs. This stage can include the negotiation phase with establishment of a joint RMA-users committee. This committee can develop an emergency plan to face resource shortage. In this paper we develop models and tools that RMA can use to determine the target resource delivery on the first stage of this decision process, but also during the negotiations of the second stage. We show how this concept of target resource delivery can be integrated in the multistage stochastic programming model by inclusion of a special distance term in the objective function. This term measures the distance between deliveries which occur under different scenarios and target delivery, therefore the resulting policy will tend to be barycentric with respect to scenario dependent deliveries. 1.2. Risk/performance trade-off The risk of resource shortage is an important feature in this application field and resource management models should take it explicitly into account. Therefore we assume that the purpose of the system management is not optimization of average costs or profits, but rather achievement of acceptable trade-off between costs/profits and risks. We call it cost/risk balanced management of scarce resource. The models for such management we obtain by extension of the multistage stochastic programming models to include explicitly the risk part, using the risk measures appropriate for the distribution of scarce resources. One such measure is the barycentric deviation from the target resource delivery outlined above. The rest of the paper is organized as follows. Section 2 sets the stage for further discussion by formulating the multiperiod stochastic programming model for distribution of scarce resources taking as a reference point the water resources. We discuss the difference between deterministic solutions for each scenario and integrated stochastic solution. This model is extended in Section 3 to include the computation of the barycentric target resource delivery. It is shown that the risk management is closely related to the concept of target delivery and how the risk/performance trade-off can be obtained from extended stochastic programming model. In Section 4 we describe an application to management of real water storage and distribution system in Sardinia. Section 5 concludes the paper with the summary of results and directions for future research.

Here we set the stage for the development of models for cost/ risk balanced management of scarce resources by formulating multistage stochastic programming model for water resources

216

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

management under uncertainty. This can be done in three phases: generation of scenarios for evolution of uncertain parameters and construction of a scenario tree, development of a deterministic optimization model for water resources management for each scenario and aggregation of these models into a multistage stochastic programming model (Birge and Louveaux, 1997; Kall and Wallace, 1994). 2.1. Construction of scenario tree The objective of this phase is to produce simplified yet adequate picture of the temporal evolution of uncertain parameters like water inflows and demands during the time horizon of planning interest. This is the stage where the specifics of the application field plays important role. First, we generate a set G of N scenarios for evolution of water inflows and demands during the time horizon of several years with a fixed time step. In Manca et al. (2004) and Pallottino et al. (2004) some water systems of south Sardinia were considered during this process. From interaction with water management professionals it became clear that historical data are of limited use due to considerable climate perturbations during the last decade. For this reason substantial part of scenarios was derived from subjective opinions of water resources experts. Each scenario g 2 G was given a weight pg which can be looked upon as a the subjective probability. Then the initial portions of scenarios were aggregated and scenarios were organized in a scenario tree as follows. The root node of the tree corresponds to the beginning of time period t = 1. From this node, n0 scenarios, of inflow and demand, start and continue in parallel for T1 periods. At t = T1 each of n0 scenarios is split into n1 scenarios all the obtained scenarios n0n1 continue in parallel for a further T1 periods until t = 2T1 when each of them is split into n2 additional scenarios. The process continues with splitting each T1 periods. Thus, scenario tree after K splittings spans the time horizon T = KT1 and consists of N scenarios,



K1 Y

ni

i¼0

An example of such a tree with T1 = 12, T = 36, K = 3, n0 = 1, ni = 3 and i = 1:2 is shown in Fig. 1. Any specific scenario g 2 G is represented by a path in this tree that starts at the root at time t = 0 and ends at one of the leaves of the tree at time t = T. The scenario set G is composed from all such paths. Usually one time period corresponds to one month, and we take T1 = 12 which corresponds to one year. This means that splittings occur at the end of each year, which conforms to the seasonal

patterns of inflows and demands. This scenario generation and aggregation process which produces a scenario tree from individual scenarios is described in more detail in Manca et al. (2004) and Pallottino et al. (2004). 2.2. Deterministic optimization model This is a linear cost minimization model which is formulated for each scenario g 2 G and has the following form:

min

cTg xg ð1Þ

A g xg ¼ b g lg 6 xg 6 ug

The vector xg includes all decision variables which describe operational and planning decisions during each time period of the planning horizon, like decisions how much water deliver to the users, how much keep in different storage components of the system, how much water to exchange between different system components, and so on. The vector of unit costs cg describe the costs of different activities like delivery costs, opportunity costs related to unsatisfied demand, opportunity cost of spilled water, etc. The set of standardized equality constraints describes the relationships between storage, usage, spill and exchange of water at different reservoirs in subsequent time periods. The right hand sides bg are formed from scenario data of inflows and demands. The lower and upper bounds lg and ug are defined by structural and policy constraints on the functioning of the system. All decision variables and data are scenario dependent, hence the index g. One specific and more detailed example of the problem (1) can be found in Section 5 dedicated to numerical experiments. 2.3. Aggregated multistage stochastic programming model for scenario optimization More precisely, this model can be referred to as the deterministic equivalent of multistage stochastic programming model, see Birge and Louveaux (1997) and Kall and Wallace (1994) for details. It is constructed from collection of deterministic models (1), as follows:

min

xg ;g2G

X

pg cTg xg

ð2Þ

g

A g xg ¼ b g ; lg 6 xg 6 ug ; x2S

8g 2 G 8g 2 G

ð3Þ ð4Þ ð5Þ

– The objective function (2) is defined as the average of the cost objectives of all scenarios weighted with by the probabilities of the scenarios, pg. – All constraints (3), (4) are collected from all scenarios and put in the aggregated model. – An additional set of nonanticipativity constraints (5) is added. These constraints ensure that the decision variables that describe decisions at time periods when scenarios are not yet split coincide. In other words, they ensure that decisions do not depend on the future. For example, the values of decision variables related to scenarios g1 and g2 from Fig. 1 must coincide during time period [0, 2T1] and decision variables related to scenarios g1, g2 and g3 must coincide during time period [0, T1], so the set of constraints (5) for this scenario tree will contain corresponding equalities.

Fig. 1. Scenario tree for K = 3, T1 = 12, n0 = 1, n1 = n2 = 3.

In Pallottino et al. (2004) authors provide some results obtained by solution of multiperiod stochastic programming model (2)–(5)

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

with scenario optimization and its comparison with deterministic solution in the case of one real water resources system when scarcity occurs. These results were referred to a two-stage, two-scenario tree. The first scenario was obtained from historical hydrological inflows while the second simulates a severe but possible shortfall in water inflows. It is derived from the first one assuming that a reduction of 50% will occur after the branching time. Resources stored in the reservoir and resources transferred to a cluster of users for stochastic and deterministic solutions are compared. Comparison shows that the deterministic policy leads to earlier emptying of reservoir for scarce scenario compared to the stochastic policy for the same scenario. The consequence of the deterministic policy is a drastic cut in water resources that can be delivered to civil and industrial communities. Stochastic policy for scarce scenario, resulting from scenario optimization, exhibits smoother resources distribution and a lower variance with respect to the deterministic policy. Thus, the management policy suggested by scenario optimization of stochastic programming model is more realistic compared to the policy that results from the deterministic optimization in the case of scarce resources. An effective management policy must be able to establish a target value for delivering resources to the demand centre. The community suffers less from resource rationing if it has been forewarned of a possible shortage. This target value should take into account the entire range of possible scenarios of resource availability, neither too pessimistic in case of abundance, nor too optimistic in case of scarcity of resources. In other words, a target value should be sufficiently balanced with respect to the different possible scenarios that could take place. In what follows we refer to this balanced target, evaluated by a balancing process among the whole set G of considered scenarios, as ‘‘barycentric’’. The more formal definition of this notion is given in Section 3, see problem (10)–(13). Establishing the resource demand level at this target value would permit notifying the resource users (the community) in a timely fashion. As a consequence, preventive measures could be adopted in order to avoid, at least in part, damages derived from an unexpected drastic cut in resources. In what follows we develop enhanced stochastic programming models that address this issue.

3. Target resource delivery and cost/risk balanced management In this section we shall be concerned with further development of the approach described in Section 2 from the perspective of relation between the Resource Management Authority (RMA) and end users. We shall see that the purely cost minimization point of view developed in the previous section is not sufficient and should be enhanced by risk management considerations. Indeed, the party which bears the risk of shortages is the end user. For this reason resource planning models employed by RMA should include the balance between costs which authority bears and risks to which the end users are exposed. We take as a starting point the general form of resource management problem of the RMA from Sections 2–5. It is also possible to formulate this problem in the node form, where nonanticipativity constraints (5) will become unnecessary due to the absence of redundant decision variables, which correspond to coinciding parts of scenarios. Solution of this problem will yield the amount of resource which will be allocated to different users during time periods of the planning horizon under different scenarios. Assuming that there is a single user (possibly consuming resource at different locations) we shall denote the set of known user’s demands, in all time periods, under scenario g as Dg. This will

217

be a subvector of the vector bg in Eq. (3). We shall also denote the set of decision variables representing resources delivered to this user in all time periods, under scenario g as ^ xg . This will be a subvector of the vector xg of all decisions of the RMA under scenario g. In the case when there is a number of users for which the RMA can have different policies, we shall index these users with index l = 1:L. Then the vectors Dg of users demands and ^ xg of resource delivery will be further subdivided into subvectors Dlg ; : Dg ¼     xlg : ^ D1g . . . ; DLg and ^ xg ¼ ^ x1g ; . . . ; ^ xLg . The vector of all demands of user l under all scenarios will be denoted by Dl ; Dl ¼ n o Dlg jg 2 G and the vector of all demands of all users under all scenarios will be denoted by D. The vector of all deliveries to the n o user l under all scenarios will be denoted by ^ xl ; ^ xl ¼ ^ xlg jg 2 G and the vector of all resource deliveries under all scenarios to all   users will be denote by ^ x; ^ x¼ ^ xg jg 2 G . We assume that the resource in question is scarce and for this reason the demand will not be satisfied in many scenarios. In such situations users should develop and adopt an emergency policy to alleviate and manage the effect of shortages on their activities. In order to do this a user l should know in advance the target level of demand satisfaction xbl that the RMA is willing to deliver to him no matter what scenario will occur. Usually this target level will be less than the user’s demand Dl, due to inherent scarcity of the resource. This difference between demand Dl and delivery xbl will represent the planned shortage of the resource, which the user l is asked to accept. Besides this planned shortage there can also be unplanned shortages when due to severe lack of resources under some scenarios the RMA will not be able to deliver even the reduced volume xbl . In order to manage this situation and develop an appropriate emergency policy, the user should be informed by the RMA about the reliability of the delivery of the target level of resource or, in other words, the quantitative level of risk that the actual delivery will fall short of the promised one. This measure  l b of risk for user l will be denoted by R ^ x ; xl . In what follows we are going to discuss different approaches which the RMA can adopt for defining this target level of delivery and the risk of not meeting this target. In order to simplify our notations, this discussion will consider the case of a single user who can actually be an aggregation of many users; the target resource delivery in this case is denoted by xb and the user’s demand by D. These are the vectors with the dimension that equals the total number of periods in the time horizon.

3.1. Expected delivery from the cost minimization The simplest way to define the target delivery is to solve the planning problem (2)–(5) and take the expected delivery as the target delivery:

xb ¼ Eg ^xg ¼

X

pg ^xg

g

Then similarly to the classic risk management theory of finance (Markowitz, 1991) the risk can be measured as the variance r2 ¼ r2 ð^x; xb Þ of deliveries:

Rð^x; xb Þ ¼ r2 ð^x; xb Þ ¼

X

pg k^xg  xb k2

g

Knowing the target delivery xb and the variance between the target and the actual delivery Rð^xl ; xb Þ, the user can now design the policy for confronting the possible resource shortages.

218

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

with additional constraints (3)–(5). Here cg(xg) is the cost associated with decision xg under scenario g and dð^xg ; xb Þ is the measure of distance between the target delivery xb and actual delivery ^ xg . In the case of Euclidean distance

Since the RMA and users are jointly responsible for the functioning of the whole system, this should be a matter of compromise between these actors. Here also we can draw from risk management approaches developed in finance. Let us look at resource distribution decisions ^ x as a portfolio of resource distribution. Then following the approach of portfolio theory (Markowitz, 1991) we shall construct the efficient frontier in the space of risk/ cost by solving the problem (9) for different values of k 2 [0, 1]. This frontier will have the shape shown in Fig. 2. Now the acceptable level of risk R⁄ will be negotiated between RMA and resource user. For the user it will include unplanned deviation around the target delivery. The weight k⁄ will correspond to this value of risk. The planned shortage is not included in this risk formulation, but it is included in the cost part instead. Similar cost/ risk balancing methodology was also utilized outside finance; see Gaivoronski and Zoric (2008) for application to collaborative delivery of advanced mobile data services. Formally speaking, the symmetric risk measure utilized in (10) considers as risk both shortage of resource delivery and excess of resource delivery. The reasons for this are twofold. From the point of view of RMA both shortage and excess carry undesirable effects and thus represent risks. Besides, the properties of the problem with a symmetric measure make it easier to solve in many cases. The part of the risk that is relevant for the users, namely the risk of shortage, can be recovered from the total risk by utilizing a multiplier that depends on the distribution of random parameters. Alternatively, some asymmetric risk measure can be used, that takes into account only the part of risk that is relevant for the end user, like expected shortfall with given level of reliability (see the problem (17)–(21) and discussion below).

dð^xg ; xb Þ ¼ k^xg  xb k2

3.3. Reoptimization

3.2. Balance between costs and risk. Defining the target resource delivery as the average resource delivery under cost minimization has the following shortcoming. It assumes that the objective of RMA is fully described by the cost minimization. The reality is more complex because the purpose of planning of the distribution of a scarce resource is to achieve a balance between sustainable maintenance of the whole system and satisfaction of the demand of end users that is in some sense ‘‘reasonable’’. Pure cost minimization may result in unacceptably high risk of not achieving the target delivery to the end user. For this reason the balance between the total costs and risks should be explicitly included in the optimization model of the type (2)–(5). This can be done similarly to the way in which the balance between risk and performance is modeled in financial risk management (Markowitz, 1991). Namely, the risk target q is fixed and the additional risk constraint is included in the resource planning problem (2)–(5) which takes the form:

X

min

pg cg ðxg Þ

ð6Þ

pg dð^xg ; xb Þ 6 q

ð7Þ

xg ;xb

X

g

g

xb ¼

X

pg ^xg

ð8Þ

g

The constraint (7) transforms into the bound on the variance of delivered quantity. The value of q defines the relative importance of cost and risk. For large q constraint (7) becomes nonbinding and (6)–(8) with (3)–(5) reduces to the cost minimization as in (2)–(5). The smaller q the higher importance of risk in cost/risk balance and for the smallest q for which the problem remains feasible (6)–(8) is equivalent to minimization of risk. Equivalently, the cost/risk balancing problem (6)–(8) can be formulated with the objective function containing both the risk and the cost terms as follows:

min ð1  kÞ xg ;xb

X

pg cg ðxg Þ þ k

g

X

! pg dð^xg ; xb Þ

ð9Þ

g

Thus, as the result of this cost/risk balancing process the user will obtain the value xb of planned delivery of the scarce resource which corresponds to the cost/risk weight k⁄ negotiated as described above and the level of risk R⁄ that the actual delivery will differ from the planned value. The value of risk can be utilized by the user to estimate the confidence intervals within which the actual delivery will be contained under assumption of approximate normality. This information can be utilized by the user to construct emergency policies for the case when the actual delivery falls short of the planned one. The RMA can also give the user its estimate of the worst shortage which could happen with respect to the planned delivery. This is done by reoptimization of the planning problem (10)–(13) for the worst possible scenario g⁄ 2 G in the case

subject to constraints (8) and (3)–(5). The parameter k can vary between 0 and 1; k = 0 corresponds to the pure cost minimization, while for k = 1 the problem becomes one of minimization of risk. Intermediate values of k provide different tradeoffs between costs and risk. Alternatively, constraint (8) can be dropped. Then in the case of Euclidean distance we call it the barycentric problem:

min xg ;xb

ð1  kÞ

Ag xg ¼ bg ; lg 6 xg 6 ug ; x2S

X

pg cg ðxg Þ þ k

g

8g 2 G 8g 2 G

X

! b 2

pg k^xg  x k

ð10Þ

g

ð11Þ ð12Þ ð13Þ

We remind that in (10) the vector ^xg of deliveries under scenario g is a subvector of the full decision vector xg. Similar to the problem (2)– (5) the vector Dg of user’s demands under scenario g enters this problem as a subvector of the vector bg of right hand sides in (11). How can the appropriate value of the weight k which balances the risk and costs be selected?

Fig. 2. Tradeoff between costs and risk.

219

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

when such a scenario is clearly identifiable. User demand in such a reoptimization problem will be taken to be equal to the planned delivery xb , this demand will form part of the right hand sides of (11). The risk term will be absent from the objective function in (9). Therefore the reoptimization problem will take the form:

min

cg ðxg Þ

ð14Þ

^g  A g  xg  ¼ b

ð15Þ

lg 6 xg 6 ug

ð16Þ

^g is constructed with xb in place of the original user’s dewhere b  mand D. The solution of this problem, xg , will be communicated to the user as the worst that can happen with regard to the delivery of scarce resource. In the case when the worst case scenario is not clearly identifiable then the problem (10)–(13) can be reoptimized for some subset G⁄ of the original scenario set G which is associated with the worst scenarios, again taking the planned delivery xb as the user’ demand. Then the worst delivery will be the smallest delivery with respect to all scenarios in G⁄. In the limit, the reoptimization may be performed on the whole set G of original scenarios with the planned delivery xb as the user’s demand and without the risk term in (10). 3.4. Guaranteed delivery with constraints on expected shortfall Up till now we have defined the planned delivery xb of scarce resource as the point which in some sense will be located in the middle of deliveries xg which will occur under different scenarios g 2 G, hence the name barycentric. Let us now adopt a different philosophy and suppose that the RMA wants to set the deliveries to some level that it will guarantee with some specified reliability. In this case the RMA will give the user the following information about the planned deliveries: – The minimal planned delivery xb which the user will obtain in (1  a) % of scenarios (or with probability 1  a). Here a is the level of reliability; it will be a small positive number defined during the negotiation process with the user. – The average shortfall to the minimal delivery which will occur in the remaining small percentage a of bad scenarios. – This can be supplemented with reoptimization in the case of the worst scenario(s), taking the guaranteed level xb as the new user’s demand, as was discussed above. Here we develop the cost/risk optimization model which will allow setting deliveries according to these principles. For the moment, let us assume that the level of reliability a is fixed and denote by Za(xb) the average shortfall from the guaranteed level xb in the a% of scenarios. We are going to set the level xb by minimizing the average shortfall from this level under structural and cost constraints. This leads to the following optimization problem:

min Z a ðxb Þ xg ;xb X pg cg ðxg Þ 6 C

ð17Þ ð18Þ

g

Ag xg ¼ bg ; lg < xg < ug ; x2S

8g 2 G 8g 2 G

ð19Þ ð20Þ ð21Þ

This problem implements the same cost/risk balance paradigm shown on the Fig. 2 as the problem 10, 11, 13. The objective function Za(xb) measures the risk which in this case is the shortfall from the guaranteed delivery xb. The upper bound C on the average costs in (18) plays the same role as the weighting parameter k in (19). For

large C the constraint (18) will become nonbinding and the problem (17)–(21) reduces to the minimization of risk. The smallest C for which the admissible set (18)–(21) remains feasible gives the solution of the problem of the cost minimization without the risk considerations. Intermediate values of C yield different compromises between minimization of costs and minimization of risk. By solving the problem (25)–(29) for different values of C we shall get the cost/ risk efficient frontier shown in Fig. 2. The delivery policy will be chosen on this efficient frontier through negotiations between the RMA (which bears costs) and the user (which bears the risks). In the rest of this subsection we show that the problem (17)– (21) is computationally feasible. This is not obvious because the objective (17) is expressed through function Za(xb) with as yet non clarified properties. However, we shall show now that the problem (17)–(21) is equivalent to a linear programming problem. The first step is to define the shortfall Z ga ðxb Þ for a fixed scenario g 2 G. This can be done in different ways, for example: T     X Z ga ðxb Þ ¼ max xbt  ^xtg ; Z ga ðxb Þ ¼ xbt  ^xtg ; Z ga ðxb Þ t

¼

T X

t¼1



max 0; xbt  ^xtg



ð22Þ

t¼1

where xbt is the t-th component of the vector xb and ^xtg is the t-th component of the vector ^xg Now (17)–(21) can be transformed as follows:

min f þ

xg ;xb ;f;yþ g

1 X p yþ 1a g g g

yþg P Z ga ðxb Þ  f; yþg

P 0;

8g 2 G

8g 2 G

ð23Þ ð24Þ ð25Þ

with additional constraints (18)–(21). This transformation is similar to the representation of the problem of CVAR minimization as LP, see Uryasev and Rockafellar (1999); Zenios (2008). Now it is necessary to select a specific expression for the shortfall. Selecting the first definition from (22) we obtain the following LP:

min f þ

xg ;xb ;f;yþ g

1 X p yþ 1a g g g

yþg  xbt þ ^xtg þ f P 0; 8g 2 G; t ¼ 1 : T yþg

P 0; 8g 2 G X pg cg ðxg Þ 6 C

ð26Þ ð27Þ ð28Þ ð29Þ

g

A g xg ¼ b g ; 8 g 2 G lg < xg < ug ; 8g 2 G

ð30Þ ð31Þ

x2S

ð32Þ

It is possible to combine this guaranteed approach to resource delivery with the barycentric approach (10)–(13). This is done by adding the following constraint



1 X p yþ 6 r 1a g g g

and constraints (27), (28) to the problem (10)–(13). Here r is the largest admissible average shortfall from guaranteed delivery in a fraction of scenarios when shortfall occurs. What is the most appropriate risk measure in the context of management of scarce resources? This is an interesting question that we are going to explore in our subsequent research. Interesting perspective on this issue is provided in Artzner et al. (1999), among others.

220

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

4. Examples and numerical experiments: a water resource system The approach described in the previous sections is implemented in the prototype of decision support system for the management of scarce water resources in the south of Sardinia, Italy. It consists of the following components: – Graphical interface for modeling a water resource system. It allows a decision maker to describe in intuitive and graphical form a water distribution network consisting of several reservoirs, several types of demand, subject to different hydrological phenomena like evaporation and infiltration. It contains the means to represent scenarios formulated by experts. – Input generator that transforms the graphical model of the water resource system into the input file for the optimization module. – Optimization module with solver. Here we utilize the commercial software available on the market, in particular CPLEX. A part of experiments was conducted with Matlab. We have conducted a series of experiments with water systems of different configurations. Here we describe an example of a simple but important reservoir-demand water system. In the scarcity conditions, the reservoir can deliver the resource (if available) in the current period or store it to deliver in a successive time-period. We assume that the dimensions of the reservoir and the demand centres are known. We want to determine the resource management policy in terms of stored water in the reservoir and amount of resource delivered over a time horizon under consideration. The purpose of this policy is to satisfy as much as possible the known resource demand and minimize the costs associated with unsatisfied demands. We consider here a water system in south Sardinia, named Flumendosa-Campidano. Here we report some results selected among a wide set of instances. We adopt a time-horizon of 4 years, comprising 48 monthly time-periods, from October ’70 to September ’74. To reach the simple reservoir-demand configuration, we consider that the main reservoirs are grouped in one with a regulation capacity obtained by adding the capacities of all reservoirs included in the system (584,1⁄106 meter3). The single demand center includes all the demand centers supplied by the reservoir. The total demand equals 235,2 ⁄106 meter3/year. For a detailed description of the Flumendosa-Campidano system we can refer to (RAS, 2005). This water system was also used as a test case in the SÉcheresse and DÉsertification dans le bassin MÉDiterranéen (SEDEMED, 2003) European Project. To validate the approach we consider both the case of fixed resource demands (the same in all time-periods) and variable resource demands (different demands in different periods). Fixed demand centres correspond, e.g., to civil, industrial and hydro electrical demand centres, and variable demand centres correspond, e.g., to agricultural demand centres. In order to provide a more transparent comparison of different solutions we report here the case of simplified structure of the scenario tree containing two scenarios g1 and g2 which differ in inflow data, maintaining the data related to the water demands equal. This means that the right hand sides bg1 and bg2 in Eq. (11), differ only in part. The branching of scenarios occurs in the 12th period. We assume that scenario g1 represents the ‘‘pessimistic’’ evolution of hydrological events, when available resources are scarce, while scenario g2 represents the ‘‘optimistic’’ evolution when sufficient resources are available. In particular, the hydrological inflows data in the scenario g2 are obtained from the historical data while those of scenario g1 are obtained assuming that a

reduction of 50% in hydrological inflows will occur after the branching time. In this way, the scenario g1 simulates a severe but possible shortfall in water inflows. We compare the behavior of stored volumes in the reservoir and resources transferred to the demand center obtained by the deterministic optimization (1) for each scenario (deterministic policy), scenario optimization using stochastic programming approach (2)–(5) (stochastic policy), and a the reoptimization phase of cost/ risk management policy (barycentric policy) putting special emphasis on the results obtained in the conditions of scarce resources. In order to get the barycentic policy we compute first the barycentric target value xb by solving the problem (10)–(13) for k = 0.5. Then we solve the problem (14)–(16) for the critical scenario g⁄ = g1 setting user demands at this target value xb in place of the original user’s demand. The solution of this problem yields the new policy to be adopted when scarce critical scenario g1 occurs, which we call barycentric policy. Figs. 3 and 4 represent the behavior of stored volumes in the reservoir and resources delivered to the demand centre in the case of fixed demands, i.e. when water demands in each scenario are the same in all periods of the time horizon. This case represents reasonably well industrial consumption. We denote it as the original demand D. Fig. 3 shows the stored volumes (measured in 106 cubic meters, Mm3) obtained by stochastic and deterministic policies for both scenarios, and those achieved by the barycentric policy in the case of the critical scenario g1, i.e. in the case of the critical shortage of resources. When scenario g2 occurs, deterministic and stochastic policies exhibit the same distribution of stored water because in this scenario the amount of resources is enough to fully satisfy the demand. On the figure they are both represented by red line1 (the two policies are overlapped). When scarce scenario g1 occurs, the deterministic policy leads to earlier emptying of the reservoir (green line) while the stochastic policy is able to store water until the end of the time horizon (blue line). Besides, Fig. 3 shows that the barycentric policy (pink line) enhances the resource distribution further. As a matter of fact this last policy allows to reach the end of the time horizon while maintaining a higher level of the stored water with respect to other policies when the critical scenario occurs. As a consequence, the decisions on stored volumes following barycentric policy better preserve the resource available in the reservoir in each time-period even with respect to the previous stochastic policy under critical conditions. Fig. 4 presents the comparison among the different policies with respect to the resources delivered to user. As before, when scenario g2 with abundant resource supply occurs, deterministic and stochastic policies produce the same behavior. On this figure both policies are represented by red line (the two policies are overlapped). In the case of this scenario the resource demand is fulfilled until the end of the time horizon. When scenario g1 with scarce resource supply occurs, results of deterministic policy are represented by the green line that coincides with the red line until the 42nd period and then drops to zero. This means that an abrupt cut of resource will occur, causing an unexpectedly heavy disruption in the user activities. The stochastic policy in the case of poor scenario g1 allows the full satisfaction of the resource demand D until the 12th time period while an increasing resources shortage can be observed from the next period to the end of the time horizon (blue line in the figure). Also this policy will cause a shortage for the user, but it is less dramatic than the shortage resulting from the deterministic policy because it avoids an unexpected full cut of resource.

1 For interpretation of color in Fig. 3, the reader referred to the web version of this article.

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

221

Fig. 3. Stored water in the reservoir-fixed demand.

Fig. 4. Transferred resource to the demand center-fixed demand.

In the reoptimization phase, the demand level is set at the target value xb obtained by adopting the poor scenario g1. The figure illustrates how the barycentric policy (pink line) enhances the performance of the system represented by the response to the demand. In the case of scarce resources, this policy allows identifying a lower demand level xb ¼ Db with respect to the original demand D that is fulfilled until the 24th period. In the following periods the delivered resource gradually decreases while maintaining a higher level of deliveries with respect to other policies. This can be considered as the preferable policy because it yields the smoother resources distribution that facilitates the arrangement of the preventive measures by the user in the face of the shortage. Figs. 5 and 6 show the behavior of stored volumes in the reservoir and resources delivered to the demand center in the case of variable demands. We have adopted the typical pattern of demand generated by agricultural production with maximums occurring during the summer months and the minimums during the winter months.

These figures exhibit the properties of the polices that are similar to the case of the fixed demand. They show better performance of the stochastic approach with respect to the deterministic one also in this case. Moreover the reoptimization phase allows reaching a better resources distribution also in the case of variable demand. Summarizing, the management policy suggested by the stochastic scenario optimization model results more risk-adapted and more implementable with respect to that obtained by the deterministic optimization in the case of scarce resources, confirming the trend observed in Pallottino et al. (2004). Besides, the reoptimization phase leads to an effective management policy that is able to establish a reduced target value for delivering resources to the demand centre under water scarcity. With respect to both cases of constant and variable demand, we observe that the barycentric target value takes into account the entire range of possible scenarios of resource availability. In the case of abundance it does not result in excessively restrictive use of resources, while in the case of scarcity it does not lead to premature

222

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

Fig. 5. Stored water in reservoir-variable demand.

Fig. 6. Transferred resource to the demand center-variable demand.

exhaustion of resources supply. In other words, the target value is sufficiently barycentric in respect to the different possible scenarios that could take place. Reducing the resource demand level to this target value can be considered as a preemptive action to mitigate the consequences of water scarcity during droughts. It would also permit the resource users (the community) to be notified in a timely fashion. This risk-adapted network can be adopted in order to avoid, at least in part, damages derived from an unexpected drastic cut in resource deliveries. The community suffers less from resource rationing if it has been forewarned of a possible shortage. Finally, Figs. 7 and 8 show the shape of the cost/risk efficient frontier obtained from solutions of the barycentric cost/risk balancing problem (10)–(13) for different values of parameter k. Fig. 7 shows the case of Flumendosa-Campidano water system with constant demand and two scenarios discussed above. Example reported Fig. 8 refers to another example with scenario tree that spans five years. Splitting of scenarios occurs at the end of each year and each node is a predecessor of three nodes. Thus, this

Fig. 7. Cost/risk frontier, barycentric risk, two scenarios.

scenario tree has 81 leaves, each leaf corresponding to one scenario. The initial part of this scenario tree corresponding to the first

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

Fig. 8. Cost/risk frontier, barycentric risk, 81 scenarios.

three splitting periods is shown Fig. 1. The barycentric problem (10)–(13) has in this case 5820 variables and 2904 equality constraints, not counting nonanticipativity constraints. Computation of cost/risk frontier from Fig. 8 was performed by solving 201 instances of this problem for different values of k between 0 and 1. It required 533 seconds on HP laptop with dual core processor running at 2.33 GHz and having 2 Gb of RAM, 36 bit architecture. Both figures show the concave dependence of costs on risk presented during the general discussion Fig. 2. The costs as expressed by linear term in (10) and risk is expressed by the square root of quadratic term in (10). Now the estimate of the size of unplanned lack of delivery can be made from the cost/risk profile shown on this figure and the acceptable cost/risk balance can be achieved by negotiations between the end users and RMA. Two observations can be made looking at Figs. 7 and 8. – It is possible to reduce substantially the risk of unplanned lack of delivery to end user(s) by increasing the costs for RMA. – The (almost) risk free policy is costly and at the low risk levels the costs can be reduced considerably by moderate increase in risk. For example, in the case shown on Fig. 8 the reduction of costs by 1/3 of the total maximal risk management budget leads to acceptance of only about 1/6 of the maximal risk value. Even if the specific application is referred to a water resources system, the presented approach can be adopted in a wide range of management problems when scarce resources occur. The study of different alternative risk/performance trade-off models is in progress providing different integrated planning and risk management models. The natural next step is to utilize developed here methodology for design of such systems. This will be the subject of our future research.

5. Conclusions In this paper we have developed a quantitative approach for cost/risk balanced planning of management of scarce resources under uncertainty and conflicting demands of different users and activities. This approach is based on the general methodology of stochastic programming/scenario optimization and utilizes the risk management tools from modern financial theory and investment science. We have been concerned here with the management of scarce resources in a given system for their storage and delivery. Adopting a risk management perspective, we defined a target barycentric resource delivery by solving an appropriate multistage stochastic

223

programming problem. This delivery level is communicated to the resource users such that they can decide their local resource management policies adapted to barycentric delivery in a timely fashion. For the worst case scenarios additional reoptimization is performed taking the barycentric level for the users demand. The reoptimization step allows to obtain the best resource management policy when even barycentric delivery level can not be met. As a consequence, preventive measures can be adopted in order to avoid, at least in part, damages derived from an unexpected drastic cut in resources. Numerical experiments confirm that this approach possess certain desirable properties from the application viewpoint, like smoother delivery patterns of scarce resources compared to the deterministic scenario optimization. Although the specific application is described with reference to a water resources system, the presented approach can be adopted in a wide range of management problems when scarce resources occur. The study of different alternative risk/performance trade-off models is in progress providing different integrated planning and risk management models. The natural next step is to utilize developed here methodology for design of such systems. This will be the subject of our future research. Another promising direction can be the utilization of stochastic dynamic programming (SDP) methodology in the context of defining the performance/risk tradeoff pursued in this paper, extending SDP approach to water reservoir management considered in Cervellera et al. (2006). Acknowledgements The authors are grateful to the anonymous reviewers for their comments that helped to improve the exposition of the paper. References Artzner, P., Delbaen, F., Eber, J.-M., Heath, D., 1999. Coherent measures of risk. Mathematical Finance 9, 203–228. Azaiez, M.N., Hariga, M., 2001. A single-period model for conjunctive use of ground and surface water under severe overdrafts and water deficit. European Journal of Operational Research 133, 653–666. Birge, J.R., Louveaux, F., 1997. Introduction to Stochastic Programming. Springer, New York. Bravo, M., Gonzalez, I., 2009. Applying stochastic goal programming: A case study on water use planning. European Journal of Operational Research 196, 1123– 1129. Cervellera, C.M.N., Chen, V.C.P., Wen, A., 2006. Optimization of a large-scale water reservoir network by stochastic dynamic programming with efficient state space discretization. European Journal of Operational Research 171, 1139–1151. Cariño, D.R., Ziemba, W.T., 1998. Formulation of the Russell-Yasuda-Kasai financial planning model. Operations Research 46 (4), 433–449. Consigli, G., Dempster, M.A.H., 1998. Dynamic stochastic programming for asset liability management. Annals of Operations Research 81, 131–162. Dembo, R., 1995. A robust approach for water resources planning under uncertainty. Annals of Operations Research 95, 313–339. Di Francesco, M., Crainic, T.G., Zuddas, P., 2009. The effect of multi-scenario policies on empty container repositioning. Transportation Research Part E 45, 758–770. Dupacová, J., Gaivoronski, A., Kos, Z., Szantai, T., 1991. Stochastic programming in water management: A case study and a comparison of solution techniques. European Journal of Operational Research 52 (1), 28–44. Ermoliev, Yu., Wets, R.J.B. (Eds.), 1988. Numerical Techniques for Stochastic Optimization. Springer Verlag, Berlin. Escudero, L.F., Monge, J.F., 2008. A model for risk minimization on water resource usage failure. International Journal of Risk Assessment and Management 10 (4), 386–403. Fleten, S.E., Kristoffersen, T.K., 2006. Short-term hydropower production planning by stochastic programming. Computers and Operations Research 35, 2656– 2671. Gaivoronski, A., de Lange, P.E., 2000. An asset liability management model for casualty insurers: Complexity reduction vs. parametrized decision rules.. Annals of Operations Research 99, 227–250. Gaivoronski, A., Zoric, J., 2008. Evaluation and design of business models for collaborative provision of advanced mobile data services: Portfolio theory approach. In: Raghavan, S., Golden, B., Wasil, E. (Eds.), Telecommunications Modeling, Policy, and Technology. Springer, New York, pp. 353–385.

224

A. Gaivoronski et al. / European Journal of Operational Research 216 (2012) 214–224

Gaivoronski, A., 2006. Stochastic optimization in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (Eds.), Handbook of Optimization in Telecommunications, Vol. 27. Springer, New York, pp. 761–799. Glockner, G.D., Nemhauser, G., 2000. A dynamic network flow problem with uncertain arc capacity: Formulation and problems structure. Operations Research 48 (2), 233–242. Hajkowicz, S., Higgins, A., 2008. A comparison of multiple criteria analysis techniques for water resource management. European Journal of Operational Research 184, 255–265. Higle, J.L., Sen, S., 1996. Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming. Dordrecht, Boston. Huang, G.H., 1998. A hybrid inexact-stochastic water management model. European Journal of Operational Research 107, 137–158. Høyland, K., Wallace, S.W., 2001. Generating scenario trees for multistage decision problems. Management Science 47 (2), 295–307. Kall, P., Wallace, S., 1994. Stochastic Programming. Wiley and Sons, New York. Kleywegt, A.J., Shapiro, A., 2001. Stochastic Optimization. In: Salvendy, G. (Ed.), Handbook of Industrial Engineering, 3rd ed. John Wiley & Sons. Loucks, D.P., Stedinger, J.R., Haith, D.A., 1981. Water Resource Systems Planning and Analysis. Prentice Hall, New York. Lucas, C., MirHassani, S.A., Poojari, C.A., Mitra, G., 2001. An application of langran relaxation to a capacity planning problem under uncertainty. Journal of the Operational Research Society 52 (11), 1256–1266. Manca, A., Sechi, G.M., Zuddas, P., Scenario Reoptimisation under Data Uncertainty, In: C. Pahl-Wostl, S. Schmidt, A.E. Rizzoli, A.J. Jakeman (Eds.), Complexity and Integrated Resources Management, iEMSs Transactions, vol.1, (2004), pp. 771– 776. Maqsood, I., Huang, G.H., Yeomans, J.S., 2005. An interval-parameter fuzzy twostage stochastic program for water resources management under uncertainty. European Journal of Operational Research 167, 208–225. Mariano-Romero, C.E., Alcocer-Yamanaka, V.H., Morales, E.F., 2007. Multi-objective optimization of water-using systems. European Journal of Operational Research 181, 1691–1707. Markowitz, H., 1991. Portfolio Selection, second ed. Blackwell.

Mulvey, J.M., Vladimirou, H., 1991. Stochastic network optimisation models for investment planning. Annals of Operation Research 20, 187–217. Pallottino, S., Sechi, G.M., Zuddas, P., 2004. A DSS for water resources management under uncertainty by scenario analysis. Environmental Modelling & Software 20 (8), 1031–1042. Pflug, G.Ch., 1996. Optimization of Stochastic Models. The Interface Between Simulation and Optimization. Kluwer, Boston. RAS (2005)–Regional Sardinian Autority, Water Resources Management Report, in Italian: Regione Autonoma della Sardegna, Piano Stralcio di Bacino Regionale per l’utilizzo delle risorse idriche, Deliberazione 17/6. Rockafellar, R.T., Wets, R.J.B., 1991. Scenarios and policy aggregation in optimization under uncertainty. Mathematics of Operations Research 16 (1), 119–147. Römisch, W., Schultz, R., 2001. Multistage stochastic integer programming: An introduction. In: Krumke, S.O., Grötschel, M., Rambau, J. (Eds.), Online Optimization of Large Scale Systems. Springer-Verlag, Berlin, pp. 581–600. Ruszczynski, A., 1997. Decomposition methods in stochastic programming. Mathematical Programming 79, 333–353. Sechi, G.M., Salis, F., Zuddas, P., 2005. Optimization Model for the Conjunctive Use of Conventional and Marginal Waters. In: Andreu, J., Rossi, G., Vagliasindi, F., Vela, A. (Eds.), Drought Management and Planning for Water Resources. T&F, pp. 73– 117. Stougie, L., Schütz, P., Tomasgard, A., 2008. Stochastic facility location with general long-run costs and convex short-run costs. Computers and OR 35 (9), 2988– 3000. Uryasev S., Rockafellar, R.T. (1999). Optimization of conditional value-at-risk. Technical Report 99-4, ISE Dept. Univeristy of Florida. Wallace, S.W., Ziemba, W.T., 2005. Applications of Stochastic Programming. MPSSIAM Series in Optimization. SIAM & MPS. Weng, S.Q., Huang, G.H., Li, Y.P., 2010. An integrated scenario-based multi-criteria decision support system for water resources management and planning–A case study in the Haihe River Basin. Expert Systems with Applications 37, 8242– 8254. Zenios, S.A., 2008. Practical Financial Optimization. Wiley-Blackwell.