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

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.