A Generalized Knapsack-Problem Based Decomposition Heuristic for Solving Multistage Stochastic Programs with Endogenous and/or Exogenous Uncertainties

作者：Zeng Zuo; Christian Brianna; Cremaschi Selen^*

来源：Industrial & Engineering Chemistry Research, 2018, 57(28): 9185-9199.

DOI：10.1021/acs.iecr.8b00822

Optimization problems with decision-dependent (endogenous) and/or decision-independent (exogenous) uncertainties are commonly observed in the process industry, and multistage stochastic programming (MSSP) is one approach for modeling such problems. However, MSSPs grow quickly and become computationally intractable for real-world size problems due to their space and time complexities. This paper presents a generalized knapsack-problem based decomposition algorithm (GKDA) to efficiently obtain feasible solutions for large-scale MSSPs under endogenous and/or exogenous uncertainties. The GKDA decomposes the original MSSP into a series of knapsack problems and solves these problems at appropriate decision points of the planning horizon. We applied GKDA to obtain feasible solutions for four planning problems, which include continuous and/or discrete decision variables, and endogenous and/or exogenous uncertain parameters. The comparison of solutions obtained by GKDA to the optimum solutions for these problems revealed that the GKDA, in most cases, yielded tight feasible solutions with solution times up to 6 orders of magnitude faster than that of the deterministic equivalents.

• 出版日期2018-7-18