(735bk) A Parametric Column-and-Constraint Generation Algorithm for Robust Optimization Under Endogenous Uncertainty

Robust optimization (RO) has garnered wide-spread interest in recent decades for solving optimization problems under uncertainty [1]. Here, uncertainty in the parameters of a problem is characterized by an uncertainty set against which we seek a robust optimal solution. In the traditional setting, the uncertainty set is exogenous (or decision-independent), i.e. the decisions taken do not have any influence on the values that the uncertain parameters can take. However, fixed uncertainty sets can be limiting or can lead to conservative solutions when the decisions affect the underlying probability distribution or the time of realization of the uncertain parameters. Such endogenous (or decision-dependent) uncertainty finds its origins in the stochastic programming literature with applications in oil/gas field development [2], capacity expansion in process networks [3], clinical trial planning [4], etc. Recently, endogenous uncertainty has also been considered in RO and the improvement in the solution quality over the traditional method that assumes fixed uncertainty sets has been shown for several examples [5, 6]. Notably, most of the existing works employ reformulation techniques to solve the problem.

Previous works exploring solution strategies have shown that cutting plane methods perform competitively for RO problems under exogenous uncertainty [7]. A typical cutting plane scheme involves a master problem that finds the optimal solution robustified against a subset of uncertain scenarios and a subproblem that finds the scenarios which cause infeasibility for a given solution [8]. In case of a fixed polyhedral uncertainty set, the number of scenarios to robustify against is limited by the number of vertices of the polyhedron. However, in case of decision-dependent uncertainty, especially when the decisions affecting the uncertainty are continuous, the cutting plane algorithm may not converge. To our knowledge, only one existing work has developed a cutting plane method using a branch & bound scheme for RO problems under decision-dependent uncertainty [9]. The proposed cutting plane method scales better compared to the reformulation approach but is limited to problems where the decisions affecting the uncertainty are discrete.

In this work, we develop a cutting plane algorithm for RO under decision-dependent uncertainty, where the decisions affecting the uncertainty can be both continuous and discrete. We propose a column-and-constraint generation strategy where the uncertain scenarios found by the subproblem are added to the master problem as constraints parametrized by the decisions affecting the uncertainty. The proposed algorithm is applied to several numerical examples, and its performance and scalability compared to the reformulation technique are also investigated.

References

1. Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization(Vol. 28). Princeton university press.
2. Goel, V., & Grossmann, I. E. (2004). A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers & chemical engineering, 28(8), 1409-1429.
3. Goel, V., & Grossmann, I. E. (2006). A class of stochastic programs with decision dependent uncertainty. Mathematical programming, 108(2), 355-394.
4. Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & chemical engineering, 32(11), 2626-2642.
5. Lappas, N. H., & Gounaris, C. E. (2018). Robust optimization for decision-making under endogenous uncertainty. Computers & Chemical Engineering, 111, 252-266.
6. Nohadani, O., & Sharma, K. (2018). Optimization under decision-dependent uncertainty. SIAM Journal on Optimization, 28(2), 1773-1795.
7. Bertsimas, D., Dunning, I., & Lubin, M. (2016). Reformulation versus cutting-planes for robust optimization: A computational study. Computational Management Science, 13, 195-217.
8. Mutapcic, A., & Boyd, S. (2009). Cutting-set methods for robust convex optimization with pessimizing oracles. Optimization Methods & Software, 24(3), 381-406.
9. Lappas, N. H. (2018). Robust Optimization for Scheduling Operations under Uncertainty [Doctoral dissertation, Carnegie Mellon University]. ProQuest Dissertations & Theses Global.