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