1 Introduction

Use of sampling approximations is a generalized approach to solve large scale stochastic nonlinear programming (SNLP) problems. Two commonly used methods to solve SNLP problems are the L-shaped method [1] and Stochastic Decomposition [2]. Monte Carlo sampling has been incorporated in the L-shaped method to avoid the scaling scenarios/samples with the number of uncertain variables. These methods though suffer from the drawback of repeated model simulation requirements which can be computationally demanding.

            This work proposes a new algorithm to overcome the computational problem associated with large scale problems with sampling. The proposed algorithm is an integration of the traditional sampling based L-shaped method with a new algorithm BONUS (Better Optimization of Nonlinear Uncertain Systems) which uses reweighting scheme to overcome the repeated model simulations

2 Methodology and results  

2.1 Sampling based L-shaped method  

In the sampling based L-shaped method, the problem is decomposed into two or multiple stages. The first stage problem (master problem) uses a linear approximation of the second stage recourse function to fix the first stage decision variables. In the second stage, these decisions are used to solve the dual of the second stage problem for different samples. The dual problem solutions give the expected value of the recourse function and generate the feasibility and optimality cuts. These cuts are added to the master problem for a better approximation of the recourse function. The method is referred to as the internal sampling method. If the second stage problem solution depends on the value of a model variable, then the model needs to be simulated for each sample in an iteration and at each such iteration.  

2.2 BONUS and reweighting  

The stochastic modeler in sampling based approaches involves model simulation for each sample which can be computationally expensive if the model is high dimensional and/or nonlinear. Recently, a new method has been proposed to solve the stochastic nonlinear programming problems, which holds its advantages by circumventing this problem of repeated model simulations. This new method is Better Optimization of Nonlinear Uncertain Systems (BONUS) [3]. The goal in stochastic programming is to improve the probabilistic objective function with each iteration. In traditional sampling based methods, this is achieved by model simulations for given number of samples and subsequent computation of the probabilistic function (e.g. expected value of the objective function). This means that with larger sample size, required for better approximation, the computational load increases. Compared to this, BONUS algorithm uses reweighting approach to skip these repeated model simulations. This reweighting scheme is central to the BONUS algorithm. The reweighting scheme allows one to calculate the probabilistic model output for a sample set, given the output for another sample set, when both the sample sets are also available. Given the two sample sets, the density function is determined at each sample point for both the distributions using Gaussian kernel density estimation [4] and weights are computed using these density estimates. These the probabilistic model output of the second sample set a function of the output for the first sample set and the computed weights. The weights are normalized to avoid computational problems.  

2.3 Proposed algorithm: L-shaped BONUS  

The proposed algorithm is an integration of the sampling based L-shaped method with BONUS. It preserves the decomposition structure of the L-shaped method and incorporates reweighting scheme from BONUS in the second stage recourse function calculation procedure. The first stage decisions are made according tot the standard L-shaped method generating the decisions and lower bound. These first stage decisions are passed on to the second stage problem where the stochastic modeling step is performed.

Since reweighting scheme needs the results for the base uniform distribution, the model is run for each sample during the first iteration of the optimization to find the model output distribution (base case distribution) and generate cuts. The first stage problem is then again solved using the newly generated cuts and the first stage decisions along with the updated lower bound are passed on to the second stage problem. During this iteration and new set of samples, the model is not re-run. The reweighting scheme predicts the probabilistic values (e.g. expectation) of the model output which is used to solve the second stage dual problem. This procedure is continued till the termination criteria for the L-shaped method is not satisfied and the stochastic modeler follows the step mentioned during the second iteration.

The advantage of the proposed algorithm is its computational efficiency as it avoids repeated model simulations. The effect is more pronounced for nonlinear and high dimensional models. The algorithm can also convert an SNLP problem into an SLP problem by using reweighting to approximate nonlinear relationships. The major concern is quality of approximation in reweighting. It has been shown that the estimation accuracy improves with increasing sample size, which also increases the computational load to a certain extent. The exact quantitative nature of this relationship expected to be problem specific. Finally, sampling properties are very important for this algorithm. The accuracy of the reweighting scheme depends on the number and uniformity of samples. For this algorithm, we propose to use the Hammersley Sequence Sampling (HSS) [5]. The sampling technique is based on the generation and inversion of Hammersley points and is shown to have k dimensional uniformity property.  

2.4 Application of L-shaped BONUS  

The proposed algorithm is applied to solve a large scale SNLP problem of placing sensors in a water distribution network to detect contaminations for security purpose. The maximum number of sensors in a network is often governed by the economics. The problem aims to find the optimum location of sensors to minimize cost and risk in face of uncertain demand at various junctions. The problem therefore fall is the category of SNLP as the relationship between uncertain demand and flow patterns is nonlinear. See [6] for problem formulation details.

Problem results show that the estimation accuracy using reweighting decreases with increasing number of uncertain variables and increases with increasing sample size. The model simulations are done in EPANET, which is a dynamic hydraulic simulator used to simulate the water distribution networks. In the standard sampling based L-shaped method, EPANET will need to be simulated for each sample to get the flow pattern which will be computationally very inconvenient, as it needs linking of the optimization code with the EPANET simulation software and running the simulation for each sample. The EPANET simulations are computationally expensive being dynamic, particularly for large networks. The proposed algorithm instead uses reweighting to bypass repeated EPANET simulations. EPANET is first simulated for a certain number of samples to get the distribution of various flow patterns. The number of samples is decided by the desired accuracy. For this work, 100 samples were used. Then for every next iteration, reweighting scheme estimates the distribution of various flow patterns. This algorithm does not need to connect the optimization code with EPANET simulator since the base case simulations can be done off-line and the results stored to be used by the optimization code.

The numerical results show that the problem solution is about 5 times faster than the standard L-shaped method for 100 samples. Moreover, the computational time scaled linearly with sample size as compared to exponentially for L-shaped method. The results show that total cost, percentage population at risk, and sensor placements change after uncertainty consideration. Without the consideration of uncertainty, the problem will be deterministic not needing the proposed algorithm for its solution. The stochastic problem would have been computationally highly demanding had it been solved by the traditional methods. The algorithm also converted an NLP problem into an LP problem.  

3 Conclusion  

The proposed algorithm overcomes the computational hurdle in SNLP problems by using reweighting scheme in the traditional set up of L-shaped with sampling algorithm. The results for the sensor placement problem show that the algorithm is a valuable tool in solving SNLP problems with considerably reduced computational burden. The sensor placement problem is particularly interesting as it is a large scale application which would have been highly complex to solve with the traditional two stage algorithm. The proposed algorithm thus holds considerable promise and needs to be investigated further to identify additional properties and application areas.  

Reference

  [1] G.B. Dantzig and P.W. Glynn. Parallel processors for planning under uncertainty. Annals of Operations Research, 22:1–21, 1990.

[2] J. Hilge and S. Sen. Stochastic decomposition: an algorithm for two stage linear programs with recourse. Annals of Operations Research, 16:650–669, 1991.

[3] K.H. Sahin and U.M. Diwekar. Better Optimization of Nonlinear Uncertain Systems (BONUS): A new algorithm for stochastic programming using reweighting through kernel denisty estimation. Annals of Operations Research, 132:47–68, 2004.

[4] B.W. Silvermann. Density estimation for statistics and data analysis. Chapman and Hall (CRC reprint 1998), Boca Raton, USA, 1986.

[5] J.R. Kalagnanam and U. Diwekar. An efficient sampling technique for off-line quality control. Technometrics, 39(3):308–319, 1997.

[6] Y. Shastri and U. Diwekar. Sensor placement in water networks: A stochastic programming approach. Journal of Water Resources Planning and Management (Accepted for publication), 2004.