(104f) Piecewise Linear Decision Rules Via Adaptive Partition for Two Stage Stochastic Mixed Integer Linear Programs

Two-stage stochastic mixed-integer linear programming (TS-SMILP) is a very challenging class of problems, especially for problems with mixed-integer second-stage variables. In process systems engineering, a large number of applications under uncertainty can be modelled using TS-SMILP [1], such as supply chain management, clinical trial, and energy systems.

However, solving TS-SMILP remains to be computationally very challenging. For TS-SMILP with discrete distribution, Küçükyavuz, and Sen [2] provide a review of the recent advances. For TS-SMILP with continuous distributions, one approach is to use sample average approximation to generate a finite number of samples. Another is the decision rule-based approach.

Decision rule-based approach has been used to solve both robust optimization and stochastic programming problems. In stochastic programming, Nasab and Li [3] apply piecewise decision rule to multistage stochastic programming. Vayanos et al. [4] propose to partition the domain of uncertain parameters into some hyperrectangles. The authors apply linear decision rules on the continuous variable in each partition and keep the binary variables constant in each partition. In robust optimization, Postek and den Hertog [5] and Bertsimas and Dunning [6] propose two adaptive splitting approaches, where the uncertainty set is iteratively split into smaller subsets and apply a linear decision rule in each subset. Other works in robust optimization include Avraamidou and Pistikopoulos [7], Feng et al. [8].

In this presentation, we propose an algorithm based on piecewise linear decision rules for TS-SMILP with continuous distributions. The domain of the uncertainty parameter is partitioned into several subsets. In each subset, the second stage continuous variables adopt a linear decision rule with respect to the uncertain parameters and the second-stage binary variables are constant. Several theoretical properties are proved. First, we prove that there exists a piecewise decision rule that is optimal for TS-SMILP. Second, under uniform partition, the convergence rate of the piecewise decision rule is proved and compared with the convergence rate of sample average approximation. In the proposed algorithm, the partition of the uncertainty set is adaptively updated. Several adaptive partition schemes including uniform partition, strong partition, and reliability partition, are proposed. The proposed algorithms are applied to an energy storage problem under demand and renewable output uncertainty. Numerical experiments suggest that the proposed algorithms have superior computational performance compared with sample average approximation in problems with low-dimension uncertain parameters.

References

[1] Li, C., & Grossmann, I. E. (2021). A Review of Stochastic Programming Methods for Optimization of Process Systems under Uncertainty. Frontiers in Chemical Engineering, 2, 34.

[2] Küçükyavuz, S., & Sen, S. (2017). An introduction to two-stage stochastic mixed-integer programming. In Leading Developments from INFORMS Communities (pp. 1 27). INFORMS.

[3] Nasab, F. M., & Li, Z. (2021). Multistage Adaptive Stochastic Mixed Integer Optimization through Piecewise Decision Rule Approximation. Computers & Chemical Engineering, 107286.

[4] Vayanos, P., Kuhn, D., & Rustem, B. (2011, December). Decision rules for information discovery in multi-stage stochastic programming. In 2011 50th IEEE Conference on Decision and Control and European Control Conference (pp. 7368-7373). IEEE.

[5] Postek, K., & Hertog, D. D. (2016). Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set. INFORMS Journal on Computing, 28(3), 553-574.

[6] Bertsimas, D., & Dunning, I. (2016). Multistage robust mixed-integer optimization with adaptive partitions. Operations Research, 64(4), 980-998.

[7] Avraamidou, S., & Pistikopoulos, E. N. (2020). Adjustable robust optimization through multi-parametric programming. Optimization Letters, 14(4), 873-887.

[8] Feng, W., Feng, Y., & Zhang, Q. (2021). Multistage robust mixed-integer optimization under endogenous uncertainty. European Journal of Operational Research.