(441e) Adaptive Robust Optimization Under Uncertainty with Regret

Authors: 
Ning, C., Cornell University
You, F., Cornell University
In recent years, decision making under uncertainty has received tremendous attention from both academia and industry [1]. Uncertainty could render the deterministic solution suboptimal or even infeasible. To this end, extensive research efforts have been made towards the development of systematic methodologies for handling uncertainty. Robust optimization has attracted considerable interest from the process systems engineering community due to its good balance between solution quality and computational tractability [2]. By introducing recourse actions, adaptive robust optimization (ARO) captures the sequential nature of decision-making processes, and is typically less conservative than static robust optimization [3, 4].

Although conventional ARO has a number of attractive features, it does not account for an important evaluation metric, known as regret, in decision-making theory [5]. In practice, the solution of an optimization problem under the presence of uncertainty is usually evaluated ex post by comparing its performance with that of the perfect information solution. The objective value of the perfect information solution is the best possible value that could be achieved by assuming that the decision maker had known the exact uncertainty realization a priori. While the perfect information solution is a utopia in the sequential decision making under uncertainty, this solution serves as an ideal benchmark for the quality of the optimized solution. The minimax regret criterion holds the promise to significantly improve the aforementioned evaluation performance, since it aims for the least deviation from the ideal benchmark.

In this work, we propose a general bi-criterion ARO (BCARO) framework that effectively accounts for the conventional robustness and minimax regret criteria. By minimizing the worst-case regret over all uncertainty realizations within an uncertainty set, the proposed framework pushes the performance of the resulting solution towards the utopia one. In this way, the evaluation performance against the ideal benchmark is significantly improved. Since the worst-case uncertainty realization is not uniquely defined for stochastic multiobjective optimization, different concepts of robust efficiency have been proposed. In this work, we employ the concept of point-based robust efficiency due to its clear interpretation and wide applications [6]. The proposed BCARO framework generates a set of Pareto-optimal solutions to reveal the systematic trade-offs between the conventional robustness and minimax regret criteria. This framework is general enough to be applied to various types of uncertainty sets, such as the polyhedral and data-driven uncertainty sets [7]. The resulting optimization problem is formulated as a bi-criterion multi-level mixed-integer programming problem, which cannot be solved directly by any off-the-shelf optimization solvers. Therefore, we further propose decomposition based algorithms for its efficient solution. To illustrate the applicability of the proposed framework, we present two applications on process network planning [8], and batch production scheduling [9]. In the process network planning problem, the proposed approach reduces the worst-case regret significantly by 52.3%, while decreasing the worst-case net present value (NPV) by merely 3.2%. In the batch production scheduling, the solution determined by the minimax regret criterion has the lowest worst-case regret of $13.6, and decreases the worst-case profit by only 0.3% compared with solution under the conventional robustness criterion.

References

[1] I. E. Grossmann, R. M. Apap, B. A. Calfa, P. García-Herreros, and Q. Zhang, "Recent advances in mathematical programming techniques for the optimization of process systems under uncertainty," Computers & Chemical Engineering, vol. 91, pp. 3-14, 2016.

[2] D. Bertsimas, D. B. Brown, and C. Caramanis, "Theory and applications of robust optimization," SIAM Review, vol. 53, pp. 464-501, 2011.

[3] A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, "Adjustable robust solutions of uncertain linear programs," Mathematical Programming, vol. 99, pp. 351-376, 2004.

[4] C. Ning and F. You, "A data-driven multistage adaptive robust optimization framework for planning and scheduling under uncertainty," AIChE Journal, vol. 63, pp. 4343–4369, 2017.

[5] D. E. Bell, "Regret in decision making under uncertainty," Operations Research, vol. 30, pp. 961-981, 1982.

[6] J. Ide and A. Schöbel, "Robustness for uncertain multi-objective optimization: A survey and analysis of different concepts," OR Spectrum, vol. 38, pp. 235-271, 2016.

[7] C. Ning and F. You, "Data-driven adaptive nested robust optimization: General modeling framework and efficient computational algorithm for decision making under uncertainty," AIChE Journal, vol. 63, pp. 3790-3817, 2017.

[8] D. Yue and F. You, "Planning and scheduling of flexible process networks under uncertainty with stochastic inventory: Minlp models and algorithm," AIChE Journal, vol. 59, pp. 1511-1532, 2013.

[9] H. Shi and F. You, "A computational framework and solution algorithms for two-stage adaptive robust scheduling of batch manufacturing processes under uncertainty," AIChE Journal, vol. 62, pp. 687-703, 2016.