(119d) LP-Based Preprocessing Algorithm and Tightening Constraints for Multiperiod Blend Scheduling Problems

Multiperiod blend scheduling problems (MBSPs) consider blending raw materials with different qualities to produce products, meeting quality specifications, over a given scheduling horizon. The objective of MBSPs is to find the least cost blending plan, subject to various constraints such as raw material availability, operational rules, and product demand requirements. A range of mixed-integer nonlinear programming (MINLP) models have been proposed for MBSPs, where binary variables are employed to model decisions on material transfers and bilinear terms are employed to model the blending process. While MBSPs arise in many engineering applications and an optimal solution may bring significant economic benefits, state-of-the-art global optimization solvers can only solve instances of modest size. Thus, improved techniques are sought to solve MBSPs of practical interest.

A major computational bottleneck for branch-and-bound-based global optimization algorithms [1] is generating lower bounds (for a minimization problem) on the optimal objective function value. Tighter lower bounds can reduce the number of branch-and-bound nodes, thus ultimately improving computational efficiency. For MBSPs, these lower bounds are computed by solving auxiliary linear-programming (LP) relaxation problems. These LPs are typically constructed by replacing the bilinear terms by various linear underestimators and relaxing the binary variables to be continuous variables. To tighten the LP relaxation, potential approaches include tightening linear underestimators for the bilinear terms and using tightening constraints based on mathematical grounds or physical insights.

This presentation describes a new LP-based preprocessing algorithm and effective tightening constraints involving integer variables (also known as integer cuts), which are applicable to both cost minimization and profit maximization MBSPs. Specifically, starting from a lifted variable reformulation [2] of the nonlinear constraints, we compute the tightest possible bounds for the lifted variables by solving LPs, for aiding in relaxing the bilinear terms. Then, based on these bounds, we propose new integer cuts that can greatly benefit from the bounds’ tightness. It is shown that the newly proposed cuts are at least as tight as the cuts proposed in [3], and are often significantly tighter. Next, new integer cuts are also developed from products that cannot be produced simultaneously within a same blender; we identify these products by solving feasibility LPs. Lastly, utilizing the mass balance of the overall blending network, we solve LPs to obtain the tightest possible bounds for the amount of raw materials that need to be processed. Based on these bounds, a third class of new integer cuts are generated to limit the number of material transfer decisions.

We consider two previously proposed and widely used MINLP formulations for MBSPs, namely the source-based formulation [4] and the PQ-formulation [5] in a multiperiod setting. Extensive numerical tests are carried out to examine the effectiveness of our new preprocessing algorithm and integer cuts in enhancing these two formulations. Numerical results show that the new preprocessing algorithm typically requires a few seconds to be executed, but the derived cuts significantly reduce the overall computational time (including preprocessing and solver solution time) to reach global optimality. Further implications and insights, for future research, are also discussed.

References

[1] Grossmann, I.E.: Advanced Optimization for Process Systems Engineering. Cambridge University Press, Cambridge (2021)

[2] Chen, Y., Maravelias, C.T.: Variable bound tightening and valid constraints for multiperiod blending. INFORMS Journal on Computing, 34(4), 2073-2090 (2022)

[3] Chen, Y., Maravelias, C.T.: Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization. Journal of Global Optimization, 77(3), 603-625 (2020)

[4] Lotero, I., Trespalacios, F., Grossmann, I.E., Papageorgiou, D.J., Cheon, M.S.: An MILP-MINLP decomposition method for the global optimization of a source-based model of the multiperiod blending problem. Computers & Chemical Engineering, 87, 13-35 (2016)

[5] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Springer, Dordrecht (2002)