(621g) Multistage Adaptive Mixed Integer Optimization Using Improved Piecewise Decision Rule

Multistage adaptive mixed integer optimization addresses dynamic decision-making problems where both continuous and integer decision variables are adjustable based on revealed uncertainty. This type of problem has many practical applications in different areas such as oilfield exploration, process capacity expansion planning, clinical trial planning, etc. The traditional method for multistage adaptive optimization relies on the scenario tree representation of the uncertainty. The optimization problem is formulated based on a number of discrete scenarios over the tree. Non-anticipativity can be enforced explicitly for scenario type formulation or implicitly for nodal formulation. While it has received lots of studies in the past, this traditional method has the limitation that it suffers from the curse of dimensionality. As the number of stages and branches increase, the tree size increases quickly. This leads to large size optimization problem and faces the computational challenge. Furthermore, the solution from this method is only guaranteed to be feasible for the scenarios considered.

Robust optimization technique provides another way to tackle uncertainty in multistage adaptive optimization. Multistage adaptive optimization with continuous variables has received much attention in the past, where integer variables are often treated as non-adaptive first stage decision to reduce the problem complexity. In this type of method, decision rules are normally introduced to make the problem computationally tractable. Ben-Tal et al. [1] introduced the usage of the linear decision rule and showed how to apply such rules to obtain the approximate optimal solution to the multistage adaptive continuous optimization problem. The linear decision rule is the most popular method used in the past. While its simple structure may lead to sub-optimality, it has the advantage of providing the required scalability to deal with multistage adaptive problems. On the other hand, variants of improved (nonlinear) decision rules were developed to improve the solution quality. As an example, Chen et al. [2] proposed an extension where the uncertainty is decomposed into the positive and negative part and then used in linear decision rule.

Piecewise linear decision rule can be regarded as a trade-off between linear decision rule and more general nonlinear decision rules. It elevates the approximation quality by having multiple slopes (i.e. decision rule coefficients) while inheriting the tractability features of linear decision rule due to its linear nature. For continuous adaptive variables, Georghiou et al. [3] introduced the piecewise linear decision rule by lifting the uncertain parameters and applying linear decision rule over the lifted uncertainty space. Bertsimas and Georghiou [4] extended the piecewise decision rule to binary adaptive variables, where the piecewise constant decision rule is obtained by apply linear decision rule over the lifted non-continuous nonconvex set. However, both methods rely on the pre-selected breakpoints for each uncertain parameter over its uncertainty range. We show that this selection significantly affects the quality of the piecewise decision rule solution. Furthermore, we propose a novel method in this work to optimize the breakpoint locations when the number of points is given. We perform computational studies to demonstrate the efficiency of this proposed method for achieving improved piecewise decision rule for multistage adaptive mixed integer optimization.

References:

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

[2] Chen, X., Sim, M., Sun, P., & Zhang, J. (2008). A linear decision-based approximation approach to stochastic programming. Operations Research, 56(2), 344-357.

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

[4] Bertsimas, D., & Georghiou, A. (2018). Binary decision rules for multistage adaptive mixed-integer optimization. Mathematical Programming, 167(2), 395-433.