(227g) Formulations and Restrictions for the Pooling and Multiperiod Pooling Problems

The pooling problem, where multiple streams are blended to produce a slate of products, has applications in many industrial sectors, including petrochemicals, water management, etc. However, solving this class of problems remains challenging for large-scale instances [1-2]. Furthermore, these traditional pooling problems can be generalized to include multiple time periods—and the associated inventories, varying supply/demand, and scheduled blending. The resulting problems, known as multiperiod pooling/blending problems (MPBPs) additionally contain integer variables to model operational constraints, notably no simultaneous inflow and outflow. MPBPs therefore represent a challenging class of mixed-integer nonlinear optimization problems, especially for increasing numbers of pools and time slots [3-5].

Given the prevalence of pooling problems in chemical engineering applications, this work begins by describing an open-source library (https://github.com/cog-imperial/pooling-network) for systematically formulating pooling problems within Pyomo [6]. Importantly, the network structure of the problem is retained, allowing our open-source solver GALINI [https://github.com/cog-imperial/galini, 7] to exploit this structure in constructing (i) a convex linear relaxation of the problem, and (ii) a mixed-integer linear programming (MILP) restriction of the problem. For the former, we draw on research efforts providing improved relaxations (a feasible point for a problem must be feasible in its relaxation), e.g., stronger formulations for the involved bilinear terms [8-9]. On the other hand, MILP-based restrictions can generate high-quality feasible points [2-3] and be incorporated in optimization strategies (a feasible point in a restriction must be feasible in the original problem). For example, Dey and Gupte [2] present a MILP-based restriction for the pooling problem and proves that optimal solutions cannot differ from that of the original model by more than a factor of N, where N is the number of output/demand nodes. Our experiments demonstrate that using this primal heuristic for large-scale, dense pooling instances greatly improves optimization performance. For the largest instances [2], our open-source solver GALINI is equivalent to, or better than, Gurobi 9.1.

Given the promise of the above MILP-based restrictions for traditional pooling problems, this work further develops MILP restrictions for MPBPs. In particular, we propose a MILP restriction for the MPBP that exploits its time-indexed and networked structure. In contrast to the standard pooling problem, we show how binary variables already used to model operational constraints in MPBP can be used in a MILP restriction that closely approximates the global optimum for many practical instances. Using several case studies, we show that solving the proposed restrictions can quickly generate good feasible solutions for MPBPs and accelerate global optimization solvers by “warm-starting.” The improvements in overall computational performance are especially important when considering the MPBP as a planning/scheduling problem, which should be re-solved as new information becomes available.

References:

[1] Alfaki, M., & Haugland, D. (2013). Strong formulations for the pooling problem. Journal of Global Optimization, 56(3), 897-916.

[2] Dey, S. S., & Gupte, A. (2015). Analysis of MILP techniques for the pooling problem. Operations Research, 63(2), 412-427.

[3] Kolodziej, S. P., Grossmann, I. E., Furman, K. C., & Sawaya, N. W. (2013). A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Computers & Chemical Engineering, 53, 122-142.

[4] Chen, Y., & Maravelias, C. T. (2020). Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization. Journal of Global Optimization, 1-23.

[5] Castro, P. M. (2015). New MINLP formulation for the multiperiod pooling problem. AIChE Journal, 61(11), 3728-3738.

[6] Hart, W. E., Laird, C. D., Watson, J. P., Woodruff, D. L., Hackebeil, G. A., Nicholson, B. L., & Siirola, J. D. (2017). Pyomo-optimization modeling in python (Vol. 67). Berlin: Springer.

[7] Ceccon, F., Baltean-Lugojan, R., Bynum, M.L., Li,C., Misener, R. (2020). GALINI: An extensible mixed-integer quadratically-constrained optimization solver. Optimization Online.

[8] Gounaris, C. E., Misener, R., & Floudas, C. A. (2009). Computational comparison of piecewise− linear relaxations for pooling problems. Industrial & Engineering Chemistry Research, 48(12), 5742-5766.

[9] Luedtke, J., D'Ambrosio, C., Linderoth, J., & Schweiger, J. (2020). Strong convex nonlinear relaxations of the pooling problem. SIAM Journal on Optimization, 30(2), 1582-1609.