(700g) Multistage Stochastic Programming Using Hybrid Scenario and Decision Rule Formulation

As an important technique for addressing dynamic decision making problem under uncertainty, multistage stochastic programming (MSSP) has received lots of applications in process systems engineering, including planning, scheduling and supply chain management. In the literature, two of the most popular approaches for solving MSSP are the scenario based method and the linear decision rule based method. In scenario based method, the uncertainty is represented by scenarios (or scenario tree for time-dependent uncertainty). The decision is scenario dependent so the model complexity is affected by the dimension of the uncertainty [1]. On the other hand, in linear decision rule method, adjustable variables are modeled as affine functions of uncertain parameters [2]. Subsequently, constraints are converted to their deterministic counterparts using duality theorem. Compared to the scenario based formulation, the model complexity is significantly reduced. Furthermore, while scenario formulation guarantees the feasibility of the solution for scenarios considered in the model, linear decision rule based solution guarantee solution feasibility for any uncertainty realization in the predefined uncertainty set.

In practical applications, uncertainty often comes from multiple sources. They can appear as objective coefficient uncertainty, constraint left-hand-side coefficient uncertainty or right-hand-side uncertainty. In addition, those uncertainties can be static or time-dependent. Simultaneously addressing those uncertainties brings challenges to the traditional scenario based or linear decision rule based method [3]. First, using only scenario based formulation can result in a very large problem size due to the presence of multiple sources of uncertainty. Therefore, the solution can be very time consuming and computationally expensive. On the other hand, it is hard to only use a decision rule based method for problems that include multiple sources of uncertainty, especially when uncertain parameters are coefficients of adjustable variables. This results in non-convex constraints with respect to uncertain parameters and thus duality theorem cannot be used for reformulation.

In this work, we propose two strategies to combine the use of scenario and decision rule in MSSP to address the above challenges. In the first approach, time-dependent uncertainties are modeled using the scenario tree and the corresponding adjustable decisions are modeled as scenario dependent. Rest static uncertainties are modeled using uncertainty sets. The corresponding semi-infinite constraints with respect to static uncertainty can be reformulated using duality theorem. This results in a scenario dependent dynamic decision solution which is robust for the static uncertainty at any nodes of the tree. In the second approach, time-dependent uncertainty is modeled using uncertainty sets and adjustable decisions are modeled using linear decision rules with respect to those uncertainties, while static uncertain parameters are modeled as discrete scenarios in finite sets and the corresponding constraints are enforced for all scenarios. The resulting semi-infinite constraints with respect to time-dependent uncertainty can further be reformulated using duality theorem. This approach leads to an adaptive decision rule solution which is feasible for defined scenarios of the static uncertainty and any realization of the time-dependent uncertainty in the uncertainty set.

Computational studies were performed to study the performance of the two approaches using a capacity expansion planning problem. MSSP problem under multiple sources of uncertainty is studied. The problem addresses the capacity expansion of a chemical plant under demand and yield uncertainties. Both methods are implemented to solve the problem. The results demonstrate that the first approach results in a larger size problem while the second approach leads to a much smaller problem which can be solved more efficiently. In addition, while the first approach has more flexibility in adjusting the binary decisions, it only leads to slightly better solution quality than the second approach. Since the second approach has much better computational efficiency, it is recommended for multistage stochastic programming problem.

References

1. A. J. Conejo, M. Carrion, J. M. Morales, Decision Making under Uncertainty in Electricity Markets, 2010, International series in operations research and management science.
2. Ben-Tal, A., Goryashko, A., Guslitzer, E., & Nemirovski, A. (2004). Adjustable robust solutions of uncertain linear programs. Mathematical Programming, 99 (2), 351-376.
3. F. Babonneau, J.-P. Vial, R. Apparigliato, Uncertainty and Environmental Design Making, 2010, International series in operations research and management science.