(407c) A Hybrid Algorithm for 2-Stage Stochastic Programming with Recourse | AIChE

(407c) A Hybrid Algorithm for 2-Stage Stochastic Programming with Recourse

Authors 

Sun, L. - Presenter, Dalian University of Technology
Pan, J. - Presenter, Dalian University of Technology

For chemical process design, various uncertain factors
appear in the form of manufacturing variations, changes in material properties, market fluctuation, etc. So uncertainty should be considered in the process design and
optimization.

2-stage stochastic programming with recourse (2-SPR) is
an important approach to process optimization
under uncertainty. It can be formulated as followings:

min   f(x) + Ee [Q(u, e)]   
                             (1)

S. t   h(x, e)
=0                                  

With   Q(u, e) =min F(x, e)  
                           (2)

S. t   g(x,
u, e)
≤0,                
                             

                              
      

Where, f(x) is the first-stage objective function. Q(u, e) is
a penalty term, which is interpreted as penalty shortfall
or corrective measures against any infeasibility, and it is the second-stage
optimization function. f(x)
+ Ee[Q(u, e)] is the objective function with recourse.
h
and g are the vectors of the equality and inequality constraints, which are derived from process models. x is structure
vector. u is operating vector. e is uncertain factor.

Mathematically, efficient algorithms need to be
developed and utilized for the
2-SPR model.

While uncertain factors have discrete probability
distribution, the 2-SPR model can
be stated as a large-scale equivalent deterministic programming. For the uncertain
factors with continuous probability distribution, the decomposition methods and approximation schemes are
required to be utilized to bring about large-scale mathematical programs, but there
are many difficulties to overcome. For example, the evaluation on the expected
value of the second-stage function (2) is an uncertain definition by the
interior optimization, and it is a sub-optimization problem embedded in the
master optimization (1). It should be integrated in the feasible region, which is
unknown at the first stage, but obtained only when the master optimization (1)
is available.

Many works have been conducted on this kind
of problems. Lerapetritou and Pistikopoulos (1994) proposed a feasible region
algorithm. Liu and Sahinidis (1996) used Monte Carlo integration schemes
instead of Gauss integration. Wang and Han(2005) proposed Monte Carlo sampling
from the entire domain of the distribution and feasibility cuts in Benders
decomposition. All these methods have their own characters.

Our work attempts to extend the prior
research in this field to propose a hybrid algorithm. Uncertain factors are
tackled by Monte Carlo sampling, and improved Benders decomposition is utilized
to deal with the problem when the master optimization can not be solved
directly. Furthermore, a new approach is derived to overcome the computation
difficulty for the model with an extremely large number of constraints. The
major steps in this approach are presented below:

Step 1:  Monte Carlo sampling.

Step 2:  To solve the dual
of the second-stage model (2), and one of three cases will arise:

Case 1: if the dual has an
unfeasible solution, the solution on the optimization problem (1) is unbounded.

Case 2: if the dual has an
optimal solution, the extreme points can be obtained to obtain the expected value of the second-stage model
(2) and the upper bound of the optimization model(1).

Case 3: if the dual is unbounded,
there is no feasible solution on the optimization model
(1).

Step 3  To rewrite the
optimization model (1) as the restricted model with more constraints.

Step 4  To solve the
restricted model with only a small subset of constraints to obtain the feasible
solutions, and then check whether these feasible solutions satisfy any of the
non-included constraints.

Step 5  To obtain the
optimal solution and the lower bound of the optimization model (1).

Step 6  If the difference
between the upper and the lower bounds is small enough for the pre-specified
tolerance, the calculation is terminated. Otherwise, return to step 2.

A case study will be presented
to demonstrate the efficacy of the algorithm.

 

Keyword: Benders decomposition; uncertainty; 2-stage
stochastic programming; Monte Carlo sampling