(260g) Graph-Structured Optimization with Multi-Parametric Programming Surrogates for Benders Decomposition

Benders decomposition [1] is a widely used method for solving large-scale mixed-integer linear programming (MILP) problems, particularly in stochastic programming, where computational complexity is a key challenge. In chemical engineering, this approach has been applied extensively—for instance, in the optimization of integrated process planning and operations [2, 3]. In this context, the Benders framework decomposes the full problem into a master problem (handling planning variables) and scenario-based subproblems (handling operational variables). However, traditional Benders decomposition requires solving optimization subproblems iteratively in every scenario, leading to significant computational overhead [4]. Moreover, the approach lacks interpretability, as it can fail to provide insight into how first-stage planning decisions propagate to second-stage operations actions under diverse forecasted uncertainties—such as energy prices, demand fluctuations, and renewable energy generation variability—which are typically captured in stochastic programming frameworks.

In this work, we propose a graph-based modeling framework that uses surrogate models based on multi-parametric (mp) programming [5, 6] to enable the modular implementation of Benders subproblems. In this approach, the stochastic program is cast as a graph in which the master node makes planning decisions and the children nodes make operational decisions. We use mp surrogates to replace the children subproblems with explicit functional mappings between planning variables, operational decisions, and uncertain parameters. These mp surrogates precompute optimal operational policies as closed-form expressions of the master problem variables and forecasted uncertainties. This enables close-to-instantaneous evaluation of primal and dual information, eliminating the need for online optimization. The proposed approach can reduce computational overhead while offering better interpretability and increased insight: the mp functions map how planning variables and forecasted uncertainties directly govern operational actions, revealing decision robustness across scenarios and identifying solutions resilient to diverse conditions.

To seamlessly integrate mp surrogates into the optimization workflow, we use a Julia framework which leverages graph-based modeling and optimization via the OptiGraph abstraction implemented in Plasmo.jl [7]. Plasmo.jl hierarchically organizes the problem into nodes and subgraphs representing master decisions and scenario subproblems. We then use the PlasmoBenders.jl [8] framework to apply Benders decomposition based on the graph structure, and define a custom solver to solve the subproblems using mp-based surrogates, enabling efficient deployment of parametric models within the decomposition structure. The mp programming problem was solved using the PPOPT solver [9], and the resulting solution along with the critical region matrices were passed to the PlasmoBenders.jl’s custom solver as mp surrogates. This graph-oriented approach not only simplifies implementation but also exploits problem sparsity to enhance scalability. We demonstrate the advantages of the framework using a chemical process expansion case study, where mp surrogates reduce solution times compared to traditional Benders decomposition while providing actionable insights into the trade-offs between capital investment and operational flexibility. The results underscore how the combination of parametric surrogates and graph-based optimization unlocks both computational efficiency and decision-making transparency in stochastic planning.

References:
[1] Rahmaniani, R., Crainic, T.G., Gendreau, M. and Rei, W., 2017. The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), pp.801-817.

[2] Iyer, R.R. and Grossmann, I.E., 1998. A bilevel decomposition algorithm for long-range planning of process networks. Industrial & Engineering Chemistry Research, 37(2), pp.474-481.

[3] Oliveira, F., Grossmann, I.E. and Hamacher, S., 2014. Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain. Computers & Operations Research, 49, pp.47-58.

[4] Saharidis, G.K., Minoux, M. and Ierapetritou, M.G., 2010. Accelerating Benders method using covering cut bundle generation. International Transactions in Operational Research, 17(2), pp.221-237.

[5] Pappas, I., Kenefake, D., Burnak, B., Avraamidou, S., Ganesh, H.S., Katz, J., Diangelakis, N.A. and Pistikopoulos, E.N., 2021. Multiparametric programming in process systems engineering: Recent developments and path forward. Frontiers in Chemical Engineering, 2, p.620168.

[6] Li, Z. and Ierapetritou, M.G., 2007. Process scheduling under uncertainty using multiparametric programming. AIChE journal, 53(12), pp.3183-3203.

[7] Jalving, J., Shin, S. and Zavala, V.M., 2022. A graph-based modeling abstraction for optimization: Concepts and implementation in plasmo. jl. Mathematical Programming Computation, 14(4), pp.699-747.

[8] Cole, D.L., Pecci, F., Guerra, O.J., Gangammanavar, H., Jenkins, J.D. and Zavala, V.M., 2025. Graph-Based Modeling and Decomposition of Hierarchical Optimization Problems. arXiv preprint arXiv:2501.02098.

[9] Kenefake, D. and Pistikopoulos, E.N., 2022. Ppopt-multiparametric solver for explicit mpc. In Computer Aided Chemical Engineering (Vol. 51, pp. 1273-1278). Elsevier.