(461a) Robust Optimization with Decision-Dependent Uncertainty Sets

Robust Optimization (RO) is a systematic approach for mitigating risk from parameter uncertainty in optimization models. Its main distinctive property is that it enforces the problem constraints for any realization of the uncertain parameters within the prescribed uncertainty set, which is typically defined as a constant set [1]. In many cases, however, uncertainty can be affected by the decision maker’s strategy (endogenous uncertainty) [2] . While this class of uncertainty has been investigated thoroughly in the Stochastic Programming (SP) literature (e.g. [3]–[6]), little has been done in the context of RO [7]. Motivated by this fact, we introduce broadly applicable decision-dependent polyhedral uncertainty sets, which allow us to capture functional changes in correlations induced by given decisions, as well as to eradicate conservatism effects from parameters that become irrelevant in view of the optimal decisions.

In this context, we investigate the numerical performance of applying the standard, duality-based reformulation approach to solve RO problems with decision-dependent sets. We also present a novel algorithmic solution approach based on the Kelley's cutting plane method [8] within a tailored branch-and-bound framework, which can improve tractability. Furthermore, we show the capability of our proposed methodology to incorporate for the first time near-optimal recourse actions, such as piece-wise linear or piece-wise constant decision rules [9], in multi-stage stage setups with endogenous uncertainty. This feature is of great importance since it has been shown [10] that deferring a subset of the decisions for later (“wait-and-see”) can lead to more profitable—yet equally robust—solutions compared to traditional RO, where all of the decisions are considered as “here-and-now”.

The modeling capabilities afforded to us by using these new decision-dependent sets is showcased via a number of case studies, for which we quantify the additional benefits that can be gained by introducing recourse actions in a non-anticipative fashion to multi-stage problems involving endogenous uncertainty.

References:

[1] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust optimization. Princeton University Press, 2009.

[2] T. W. Jonsbråten, R. J. B. Wets, and D. L. Woodruff, “A class of stochastic programs with decision dependent random elements,” Ann. Oper. Res., vol. 82, pp. 83–106, 1998.

[3] V. Gupta and I. E. Grossmann, “A new decomposition algorithm for multistage stochastic programs with endogenous uncertainties,” Comput. Chem. Eng., vol. 62, pp. 62–79, 2014.

[4] V. Gupta and I. E. Grossmann, “Solution strategies for multistage stochastic programming with endogenous uncertainties,” Comput. Chem. Eng., vol. 35, no. 11, pp. 2235–2247, 2011.

[5] S. Solak, J. P. B. Clarke, E. L. Johnson, and E. R. Barnes, “Optimization of R&D project portfolios under endogenous uncertainty,” Eur. J. Oper. Res., vol. 207, no. 1, pp. 420–433, 2010.

[6] R. M. Apap and I. E. Grossmann, “Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties,” Manuscr. Prep., 2015.

[7] M. Poss, “Robust combinatorial optimization with variable cost uncertainty,” Eur. J. Oper. Res., vol. 237, no. 3, pp. 836–845, 2014.

[8] J. E. Kelley, Jr., “The Cutting-Plane Method for Solving Convex Programs,” J. Soc. Ind. Appl. Math., vol. 8, no. 4, pp. 703–712, 1960.

[9] D. Bertsimas and A. Georghiou, “Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization,” Oper. Res., vol. 63, no. 3, pp. 610–627, 2015.

[10] A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski, “Adjustable robust solutions of uncertain linear programs,” Math. Program., vol. 99, no. 2, pp. 351–376, 2004.