(520a) Uncertainty Set Induced Robust Linear and Mixed Inter Linear Optimization and Their Probabilistic Guarantees: New Results and Comparative Study

In the vast majority of optimization applications, problem data are often subject to uncertainty due to their random nature, measurement errors or other reasons. The solution obtained without considering the data uncertainty may be suboptimal or even infeasible for practical applications. Thus, addressing uncertainty issues in optimization is of significant importance and has received a lot of attention in both academia and industry.

Robust optimization belongs to an important methodology dealing with optimization problems with data uncertainty. With a predefined set within the uncertain space, robust optimization techniques aim at finding the best solution which is feasible for any realization of the data uncertainty in the given set. The corresponding optimization problem is also called robust counterpart optimization problem.

Robust optimization has received lots of attention in the process operations applications [1], [2].  Lin et al., [3] and Janak et al., [4] extended the robust optimization formulation introduced for linear programming problems [5] to mixed integer linear optimization (MILP) problems and apply the method to process scheduling problem. Verderame and Floudas [6] studied both continuous (general, bounded, uniform, normal) and discrete (general, binomial, Poisson) uncertainty distributions and applied the robust optimization framework to operational planning problems. The work was further compared with the conditional-value risk based method [7].

In this work, we report our recent results on robust counterpart optimization techniques for linear optimization and mixed integer linear optimization problems, and perform a comparative study on the different robust formulations [8]. Specifically, different uncertainty sets, including those studied in literature (i.e., interval set [9]; combined interval and ellipsoidal set [5, 10]; combined interval and polyhedral set [11]) and new ones (i.e., adjustable box; pure ellipsoidal; pure polyhedral; combined interval, ellipsoidal, and polyhedral set) are studied in this work and their geometric relationship is discussed. For uncertainty in the left hand side, right hand side, and objective function of the optimization problems, robust counterpart optimization formulations induced by those different uncertainty sets are derived. Probabilistic guarantees on constraint violation are also derived for the above different uncertainty sets induced robust counterpart optimization models, for both bounded and unbounded uncertainty, with and without detailed probability distribution information.

Extensive numerical studies are performed to compare the solutions of the robust counterpart optimization models and the tightness of the different probability bounds, and also to assess the conservatism of several important robust counterpart optimization models. Applications in refinery production planning and batch process scheduling problems are presented. The usage of probability distribution information is introduced and tighter a priori probability bounds are proposed so as to find better robust solutions in these applications [8].

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

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

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

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

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

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

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

8.            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: p. In publication.

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

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

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