(120b) A Branch and Bound Algorithm to Solve Large-Scale Multistage Stochastic Programs

Multistage stochastic programing is a scenario-based approach for optimization under uncertainty (Birge & Louveaux, 2011). In chemical engineering, MSSPs are used to find optimal decisions in oil field investment planning, clinical trial scheduling, and process synthesis under uncertainty. The MSSP problem structure consists of three parts. The first part is a set of constraints for each scenario sub-problem. The remaining two parts are blocks of non-anticipativity constraints, which relate the decision variables in each scenario sub-problem to ensure that the outcomes of uncertain parameter(s) are not anticipated. The ability to generate the MSSP formulation for large-scale problems becomes prohibitive due to the rate at which the number of equations and variables grows with problem size. Increasing the number of uncertain parameters or the number of realizations for each uncertain parameter causes exponential growth in the number of scenarios. As such, there is great opportunity to develop exact solution approaches, which reduce the size of the problem formulation. Some recent examples of this type of work in chemical engineering include Colvin and Maravelias (2010) where the clinical trial planning problem formulation size is reduced by gradually adding non-anticipativity constraints that are violated with the in progress solution. Gupta and Grossmann (2011) presented a Lagrangean decomposition strategy, which solved the Lagrangean problem with relaxed conditional non-anticipativity constraints and dualized first time-period constraints to bound the solution. The authors then use a heuristic approach to find a feasible solution.

In this work, we present a branch and bound algorithm to solve multistage stochastic programs. For the algorithm we compare two different relaxation approaches for generating infeasible bounds. The first approach utilizes a modified progressive hedging approach. Progressive hedging is an augmented-Lagrangean-inspired scenario decomposition strategy, which iteratively converge to the optimal solution of stochastic programs (Rockafellar & Wets, 1991). The approach is shown to be provably optimal for multistage stochastic programs with decision independent uncertainty and continuous variables (Watson & Woodruff, 2011). In order to apply the algorithm to MSSPs with endogenous uncertainty and integer variables, we relax all integrality constraints of the problem and relax the conditional non-anticipativity constraints which cannot be treated as exogenous. Applying the progressive hedging approach results in solving a set of individual modified scenario sub-problems until variance in the decision variables is sufficiently small. The advantage of using the progressive hedging approach is that scenario sub-problems are able to completely separated which allows for easy parallelization.

The second approach bounds the problem by solving the MSSP without enforcing any non-anticipativity constraints. This approach provides a weaker bound than the progressive hedging approach, however, the scenario sub-problems are completely independent of each other and do not require multiple iterations in order to converge. This approach may be particularly useful when the size of the scenario set is prohibitively large. The feasible bound is generated using a memory efficient knapsack problem based decomposition heuristic (Christian & Cremaschi, 2015).

Computational studies were performed on case studies of the pharmaceutical R&D pipeline management problem originally presented in Colvin and Maravelias (2008). Results from the work show that the algorithm generates feasible bounds and bounds these solutions efficiently for instances of the clinical trial planning problem using either the progressive hedging bounding approach or Optimally solving Scenario Sub-problems (OSS) without enforcing non-anticipativity constraints. In both cases, the memory requirements were lower than the memory needed to generate the MSSP formulation. In the case of the OSS approach, the algorithm solved a seven-product instance of the pharmaceutical clinical trial planning problem with more than 11 million binary variables and 249 million constraints to a 7% optimality gap. Memory savings in the algorithm was found to be highest in the largest case studies, where the effect of the problem scaling is most noticeable.

References

Birge, J. R., & Louveaux, F. (2011). Introduction to Stochastic Programming. Springer New York.

Christian, B., & Cremaschi, S. (2015). Heuristic solution approaches to the pharmaceutical R&D pipeline management problem. Computers and Chemical Engineering, 74, 34–47.

Colvin, M., & Maravelias, C. T. (2008). A stochastic programming approach for clinical trial planning in new drug development. Computers & Chemical Engineering, 32, 2626–2642. http://doi.org/10.1016/j.compchemeng.2007.11.010

Colvin, M., & Maravelias, C. T. (2010). Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming. European Journal of Operational Research, 203(1), 205–215. http://doi.org/10.1016/j.ejor.2009.07.022

Gupta, V., & Grossmann, I. E. (2011). Solution strategies for multistage stochastic programming with endogenous uncertainties. Computers and Chemical Engineering, 35(11), 2235–2247. http://doi.org/10.1016/j.compchemeng.2010.11.013

Rockafellar, R. T., & Wets, R. J.-B. (1991). Scenarios and Policy Aggregation in Optimization Under Uncertainty. Mathematics of Operations Research, 16(1), 119–147.

Watson, J. P., & Woodruff, D. L. (2011). Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Computational Management Science, 8(4), 355–370. http://doi.org/10.1007/s10287-010-0125-4