262788 Advances in Robust Optimization: Improving the Solution Quality and Addressing Uncertainty Parameter Correlation in Planning and Scheduling

Tuesday, October 30, 2012: 3:15 PM
326 (Convention Center )
Zukui Li and Christodoulos A. Floudas, Chemical and Biological Engineering, Princeton University, Princeton, NJ

Among the various methods for addressing uncertainty in mathematical optimization problem, robust optimization is a type of rigorous yet efficient technique that can lead to solution robustness/reliability. Except the contribution from operations research community (e.g., [1-4]), robust optimization has also received lots of attention in the chemical process systems engineering community [5-6]. Specifically, Lin et al. [7] and Janak et al. [8] developed the theory of the robust optimization framework for general mixed-integer linear programming problems and considered both bounded and several known probability distributions. The robust optimization framework was later extended by Verderame and Floudas [9] for both continuous (general, bounded, uniform, normal) and discrete (general, binomial, Poisson) uncertainty distributions. The work was further compared with the conditional value-at-risk based method in Verderame and Floudas [10].

In our recent work [11-12], we systematically studied the set induced robust counterpart optimization technique for linear and mixed integer linear optimization problems. Different uncertainty sets are studied and their corresponding robust counterpart optimization formulations for both linear and mixed integer linear optimization problems are derived [11]. A priori and a posteriori probabilistic guarantees on constraint satisfaction for the robust solution of those different uncertainty set induced robust counterpart optimization models are developed, for both bounded and unbounded uncertainty, with and without detail probability distribution information [12].

Although significant progress has been made, there are several important issues which restrict the efficient application of robust optimization. First, the quality of the robust solution was often ignored in the past. In other words, while the desired solution feasibility (i.e., probability of constraint satisfaction) is met, how far is the solution from optimality? Can we find better robust solution while still satisfying the same probability requirements? Second, the issue of correlation between different uncertain parameters is often ignored in many applications.

To address the above issues, we make several advances for the robust optimization method. First, we propose a novel strategy for improving the robust solution using the a priori and a posteriori probability bounds developed in our recent work [11-12], where it has been shown that the a posteriori probability bound is in general tighter than the a prior probability bounds. Based on this fact, we developed an iterative solution framework which combines the advantage of robust optimization and the a priori/a posteriori probability bounds. The proposed method can essentially improve the solution quality of classical robust optimization framework without significant computational efforts. Comparing to the classical single-step robust optimization method, the quality of the robust solution can be improved while the same probabilistic guarantee on constraint satisfaction is still met. Second, we study the issue of correlation between different uncertain parameters in constraints, and developed robust counterpart optimization models for both linear and quadratic type correlations, which further provides a technique support for the application of the robust counterpart optimization in practical problems. The effectiveness of the proposed methods is illustrated through numerical examples and its application in planning and scheduling problems will be presented.

References:

1. Soyster, A.L., Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 1973. 21: p. 1154-1157.

2. Ben-Tal, A. and A. Nemirovski, Robust solutions of uncertain linear programs. Operations Research Letters, 1999. 25(1): p. 1-13.

3. Ben-Tal, A. and A. Nemirovski, Robust solutions of Linear Programming problems contaminated with uncertain data. Mathematical Programming, 2000. 88: p. 411-424.

4. Bertsimas, D. and M. Sim, The price of robustness. Operations Research, 2004. 52(1): p. 35-53.

5. Verderame, P.M., et al., Planning and Scheduling under Uncertainty: A Review Across Multiple Sectors. Industrial & engineering chemistry research, 2010. 49(9): p. 3993-4017.

6. Li, Z. and M.G. Ierapetritou, Process scheduling under uncertainty: review and challenges. Computers and Chemical Engineering, 2008. 32: p. 715-727.

7. Lin, X., S.L. Janak, and C.A. Floudas, A new robust optimization approach for scheduling under uncertainty: I. bounded uncertainty. Computers and Chemical Engineering, 2004. 28: p. 1069-1085.

8. Janak, S.L., X. Lin, and C.A. Floudas, A new robust optimization approach for scheduling under uncertainty: II. Uncertainty with known probability distribution. Computers and Chemical Engineering, 2007. 31: p. 171-195.

9. Verderame, P.M. and C.A. Floudas, Operational Planning of Large-Scale Industrial Batch Plants under Demand Due Date and Amount Uncertainty. I. Robust Optimization Framework. Industrial & Engineering Chemistry Research, 2009. 48(15): p. 7214-7231.

10. Verderame, P.M. and C.A. Floudas, Operational Planning of Large-Scale Industrial Batch Plants under Demand Due Date and Amount Uncertainty: II. Conditional Value-at-Risk Framework. Industrial & Engineering Chemistry Research, 2010. 49(1): p. 260-275.

11. Li, Z., R. Ding, and C.A. Floudas, A Comparative Theoretical and Computational Study on Robust Counterpart Optimization: I. Robust Linear and Robust Mixed Integer Linear Optimization. Ind. Eng. Chem. Res, 2011. 50: p. 10567-10603.

12. Li, Z. and C.A. Floudas, A Comparative Theoretical and Computational Study on Robust Counterpart Optimization: II. Probabilistic Guarantees on Constraint Satisfaction. Ind. Eng. Chem. Res., 2012: p. in press.


Extended Abstract: File Not Uploaded
See more of this Session: Planning and Scheduling II
See more of this Group/Topical: Computing and Systems Technology Division