(441f) Hybrid Decision Rules in Multistage Adaptive Optimization

Multistage adaptive optimization is an important technique for addressing dynamic decision making problem under uncertainty. It has been employed in numerous process systems engineering applications, including planning, scheduling and supply chain management. The optimal solution of a multistage adaptive optimization problem can be cast as a set of decision policies/functions of the uncertainty. While the presence of the uncertainty induces a set of semi-infinite constraints that are computationally intractable, various approximation methods have been used in the past.

The first method approximates the decision policy through a discrete set of scenario dependent decision values. For instance, scenario-based multistage stochastic programming has been extensively used in different areas, where uncertainty is characterized with a finite number of scenarios using a scenario tree. The stochastic problem can then be reformulated into a deterministic one with the scenarios: the objective function is calculated as the expectation and the constraints are enforced based on scenarios. However, this method suffers from the curse of dimensionality: the problem size can quickly increase as the dimension of the uncertainty increases. The second method relies on decision rules, which has received increasing attention in recent years for solving such problems. In this type of method, the adaptive decisions are approximated as a function of the observed uncertainty to reduce the model complexity. The simplest type of decision rule, a linear decision rule (LDR), assumes an affine relationship between the decision and uncertain parameters. Using an LDR, strong duality of convex optimization can often be utilized to construct the tractable counterpart of the stochastic problem. The significance of the approach was demonstrated by Ben-Tal et al. [1].

While the LDR method can lead to significant computational advantage compared to the scenario method, its solution quality is limited by its simplicity. To address this limitation, several variants of nonlinear decision rules have been proposed to improve the approximation quality, but with increased computational load (e.g. [2]). The decision rule based method is governed by two competing objectives: tractability and approximation quality. A piecewise linear decision rule (PLDR) can be regarded as a special type of nonlinear decision rule. It elevates the approximation quality by having multiple slopes (i.e. decision variables) while inheriting the tractability features of an LDR due to its linear nature [3]. In this work, we investigate the hybrid strategy of using LDRs and PLDRs for solving multistage adaptive optimization. Several guiding strategies were proposed towards reaching a good balance between computational complexity and solution quality.

First, we investigate how best to lift an uncertainty set while using PLDR in multistage adaptive optimization. We demonstrate that defining a hybrid decision rule where the uncertainties in the near future are modelled with more details than later stages is attractive. The modelling detail of the uncertainty is reflected by the number of breakpoints used for lifting; the more breakpoints used to lift the uncertainty set, the more detailed is the uncertainty represented. This is similar to a construct used in scenario-based stochastic programming in which a scenario tree contains many branches per node (i.e. captures more detail) in early stages and relatively few branches per node (i.e. captures less detail) in later stages can be attractive [4]. The proposed method is applied to a multistage stochastic transportation problem and the trade-off between solution quality deterioration and computational load reduction is promising. Second, we study the dependence on the history of observed uncertainty in the decision rule. Ideally, decision rules are defined as a function of the full history of observed uncertainty. Nonetheless, solving a multistage adaptive optimization problem with full history LDR can be computationally challenging [5]. In this work, we exploit the correlation in the uncertainty to restrict the history dependence to reduce the computational load. We show empirically via the multistage stochastic newsvendor problem a relationship between the correlation lag in the uncertainty set and the minimum history lag in the decision rule required for a satisfactory trade-off between deterioration in solution quality and reduction in the computational burden.

References

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

[2] D. Bertsimas, D. A. Iancu, and P. A. Parrilo. A hierarchy of near-optimal policies for multistage adaptive optimization. IEEE Transactions on Automatic Control, 56(12): 2809–2824, 2011.

[3] A. Georghiou, W. Wiesemann, and D. Kuhn. Generalized decision rule approximations for stochastic programming via liftings. Mathematical Programming, 152(1-2):301–338, 2015.

[4] A. N. Arslan and D. J. Papageorgiou. Bulk ship fleet renewal and deployment under uncertainty: A multi-stage stochastic programming approach. Transportation Research Part E: Logistics and Transportation Review, 97:69–96, 2017.

[5] M. Ang, Y. F. Lim, and M. Sim. Robust storage assignment in unit-load warehouses. Management Science, 58(11):2114–2130, 2012.