(19d) A Branch-and-Bound Scheme for K-Adaptability Problems in Robust Optimization

Multi-stage decision-making problems, in which a sequence of decisions must be made over time, both in anticipation of and in response to the realization of uncertain problem parameters, arise in a wide variety of engineering and management applications. Besides faithfully modeling the dynamic nature of decision-making processes in practice, multi-stage problems are essential to mitigate the conservatism of traditional single-stage problems. However, despite intensive research efforts, multi-stage optimization problems continue to pose several theoretical and computational challenges.

Amongst the various methodologies that have been proposed to address such problems, robust optimization [1] has received a lot of attention over the last decade since it avoids many of the shortcomings associated with traditional approaches. In particular, it replaces probability distributions with uncertainty sets as the fundamental models of uncertainty and seeks to determine decisions that remain feasible for any realization of the uncertainty from within the modeled uncertainty set.

While multi-stage robust optimization problems involving continuous recourse decisions have been well-studied [1, 2], the literature on problems involving discrete recourse decisions is relatively sparse. In the special case of two-stage problems in which the uncertainty appears only in the constraint “right-hand sides,” a nested column-and-constraint generation solution approach that converges in finite time is developed in [3]. Other approaches are concerned with the design of conservative approximations of the true multi-stage problem and fall into one of three categories: (i) decision rule approaches, in which the recourse decisions are modeled as explicit functions of the uncertainty [4, 5]; (ii) uncertainty set partitioning approaches, in which the recourse nature of discrete decisions is simulated by designing separate sets of decisions for different, pre-specified subsets of the uncertainty set [6, 7]; and (iii) K-adaptability approaches, in which K sets of discrete recourse decisions are designed before the uncertainty is resolved and the best decision is implemented after observing the actual realization of the uncertainty [8, 9].

In this work, we focus on the K-adaptability approach to address two-stage robust optimization problems. In contrast to the other two approaches, K-adaptability has been shown to provide a remarkably good approximation of the true problem, both in theory and numerical experiments [8, 9]. Furthermore, rather than designing the optimal recourse decision for every possible realization of the uncertainty [3], it aims to design a small number of contingency plans, which may be preferable for operational or organizational reasons.

Existing solution approaches for K-adaptability problems are either heuristic [8] or consist of reformulating the problem as a finite-dimensional mixed-integer linear program under the additional assumption that both the first- and second-stage decisions are binary [9]. In this work, we alleviate both of these shortcomings and devise a solution scheme that is both exact and applicable for problems featuring mixed-integer decisions and constraints with uncertainty affecting their “left-hand sides.” By viewing the K-adaptability problem as a semi-infinite disjunctive program, our solution scheme uses a sampling-based disjunctive branch-and-bound search procedure to asymptotically converge to an optimal solution. For problems with uncertainty sets of finite cardinality, our solution scheme converges in finite time. In addition to our convergence proof, we also analyze the solvability, convexity and tractability properties of general K-adaptability problems, and present conditions under which they reduce to single-stage (also known as static) robust optimization problems, and under which their optimal values coincide with that of the true two-stage problem.

Extensive numerical experiments conducted on benchmark data from a number of applications demonstrate that: (a) we can significantly improve upon decisions determined via static robust optimization within small computing times, and (b) our solution scheme for K-adaptability problems is a practically tractable approach for addressing two-stage robust optimization problems that improves upon the current state-of-the-art.

References:

 [1] D. Bertsimas, D.B. Brown, and C. Caramanis (2011). Theory and applications of robust optimization. SIAM Review, 53(3):464—501.

[2] A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski (2004). Adjustable robust solutions of uncertain linear programs. Mathematical Programming A, 99(2):351—376.

[3] L. Zhao and B. Zeng (2012). An exact algorithm for two-stage robust optimization with mixed integer recourse problems. Technical report, University of South Florida.

[4] D. Bertsimas and A. Georghiou (2015). Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Operations Research, 63(3):610—617.

[5] D. Bertsimas and A. Georghiou (2014). Binary Decision Rules for Multistage Adaptive Mixed-Integer Optimization. Available on Optimization Online.

[6] D. Bertsimas and I. Dunning (2016). Multistage Robust Mixed-Integer Optimization with Adaptive Partitions. Operations Research, 64(4):980-998.

[7] K. Postek, D. den Hertog (2016). Multistage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty Set. INFORMS Journal on Computing, 28(3):553—574.

[8] D. Bertsimas and C. Caramanis (2010). Finite adaptability in multistage linear optimization. IEEE Transactions on Automatic Control, 55(12):2751—2766.

[9] G.A. Hanasusanto, D. Kuhn, W. Wiesemann (2015). K-Adaptability in Two-Stage Robust Binary Programming. Operations Research, 63(4):877—891.