# (12g) Efficient Optimization Algorithm for Large Scale Problems in Nonlinear Stochastic Programming

#### AIChE Annual Meeting

#### 2005

#### 2005 Annual Meeting

#### Computing and Systems Technology Division

#### Advances in Optimization I

#### Monday, October 31, 2005 - 10:00am to 10:20am

**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.

### Checkout

This paper has an Extended Abstract file available; you must purchase the conference proceedings to access it.

### Do you already own this?

Log In for instructions on accessing this content.

### Pricing

####
**Individuals**

AIChE Pro Members | $150.00 |

AIChE Graduate Student Members | Free |

AIChE Undergraduate Student Members | Free |

AIChE Explorer Members | $225.00 |

Non-Members | $225.00 |