(441g) An Algorithmic Cutting Plane Method for Solving Robust Optimization Problems with Endogenous Uncertainty

Robust Optimization (RO) is one of the major systematic approaches for mitigating effects of parameter uncertainty in mathematical optimization models [1]. The fundamental characteristic of RO is that it seeks the best possible solution that remains feasible for every possible realization of uncertainty within a postulated uncertainty set. The selection of the uncertainty set itself is of critical importance, since it can affect both the optimality of the solution, as well as the level of risk against which it is hedged.

Traditionally in the RO literature, uncertainty sets are constructed under the assumption that the decision maker’s strategy cannot have an impact on the realization of uncertainty (“exogenous uncertainty”). However, there are well documented cases from the Stochastic Programming literature where the realization of uncertainty and/or its underlying distributional support can be affected by the decisions of the policy makers (“endogenous uncertainty”) [2], with examples including oilfield production planning [3,4], R&D portfolio optimization [5], capacity expansion [6], clinical trial planning [7] and network interdiction [8], among others.

Recently, Lappas & Gounaris [9] proposed the extension of the traditional polyhedral uncertainty sets to decision-dependent uncertainty sets (DDUS), and showcased the flexibility of the introduced modelling capabilities in terms of capturing the effects of endogenous uncertainty in a variety of relevant problems, while maintaining the favorable computational tractability characteristics of RO. The solution approach utilized was based on a reformulation of the original problem to a monolithic robust counterpart. While the presented methodology is sufficient for small sized problems and continuous valued uncertain parameters, it can be limiting if the reformulated model is of size prohibitive to be loaded in memory, or when the uncertainty set involves uncertain parameters of discrete nature. The limitations of the reformulation approach become even more pronounced when a decision rule scheme is desired in the context of multi-stage decision-making contexts [10].

To alleviate the above limitations of the reformulation approach, we propose a novel algorithmic cutting plane method for solving robust optimization problems with endogenous uncertainty. In particular, we develop a branch & bound algorithm that gradually enforces the robustness of the solution by hedging against violating scenarios that are relevant to the optimal decision strategy. A comprehensive computational study across various problems illustrates the computational advantages of the proposed algorithm over the old reformulation approach, while the impact of various algorithmic enhancements is also investigated. Finally, the flexibility of the new algorithmic approach is presented with problems involving discrete uncertain parameters and elaborate decision-rule schemes.

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,” Annals of Operations Research, vol. 82, pp. 83–106, 1998.

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

[4] R. M. Apap and I. E. Grossmann, “Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties,” Computers & Chemical Engineering, vol. 103(8), pp.233-274, 2017.

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

[6] V. Goel and I. E. Grossmann, "A class of stochastic programs with decision dependent uncertainty" Math. Program., vol, 108 (2–3) , pp. 355-394, 2006.

[7] M. Colvin and C. T. Maravelias, "A stochastic programming approach for clinical trial planning in new drug development." Computers & Chemical Engineering, vol. 32(11), pp. 2626-2642, 2008.

[8] S. Peeta, F. S. Salman, D. Gunnec, and K. Viswanath, "Pre-disaster investment decisions for strengthening a highway network.", Computers & Operations Research, vol. 37(10), pp. 1708-1719, 2010.

[9] N.H. Lappas and C. E. Gounaris, "Robust Optimization for decision-making under endogenous uncertainty.", Computers & Chemical Engineering, vol. 111(3), pp. 252-266, 2018.

[10] D. Bertsimas, and A. Georghiou, "Design of near optimal decision rules in multistage adaptive mixed-integer optimization.", Operations Research, vol. 63(3), pp. 610-627, 2015.