(468a) Global Optimization of the Multiperiod Blending Problem Via a Logic-Based Decomposition with Symmetry-Breaking Cuts

The pooling problem is an important problem within the field of chemical engineering, which initially arose from the oil industry. Given the bilinear nature of the problem, this problem still remains challenging for state-of-the-art quadratic solvers to date. One of the extensions of the pooling problem is the Multiperiod Blending Problem (MPBP) first introduced by Kolodziej et al. [1] which considers a temporal version of the pooling problem with tanks. Binary variables are used for flow existence at each arc, making this a Mixed-Integer Quadratically Constrained Program (MIQCP). Lotero et al. [2] extended this MIQCP by formulating it as a Generalized Disjunctive Program (GDP), making it more inherently available to decompositions.

We propose an improved decomposition that solves major issues present in Lotero et al. [2]. They solve the MPBP using a two-stage decomposition algorithm that exploits the fact that bilinearities are only required when in the charging state. One of the disadvantages of the decomposition is the fact that the authors never considered the idle state of the tank. We find the symmetry caused by the lack of an idle tank scenario which can lead to additional iterations for idle tanks. We propose a symmetry breaking cut that does not cut off the optimal solution and breaks this symmetry.

We develop 60 challenging MPBP instances that improve upon instances in the literature. We show that this improved decomposition performs better than the previous decompositions for this problem [2, 3], and it also performs better than Gurobi directly applied on the MIQCP formulation despite recent advancements in MIQCP solvers. Furthermore, it achieves a substantial reduction, around 90%, in the number of bilinear constraints in subproblems, which translates into a two order-of-magnitude improvement in subproblem computational times.

References

[1] S. P. Kolodziej, I. E. Grossmann, K. C. Furman, and N. W. Sawaya, “A discretization-based approach for the optimization of the multiperiod blend scheduling problem,” Computers & Chemical Engineering, vol. 53, pp. 122–142, 2013.

[2] B. Lotero, F. Trespalacios, I. E. Grossmann, D. J. Papageorgiou, and M.-S. Cheon, “An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem,” Computers & Chemical Engineering, vol. 87, pp. 13–35, 2016.

[3] D. Ovalle, J. L. Pulsipher, C. Gomez, J. M. Gomez, C. D. Laird, M. G. Drouven, and I. E. Grossmann, “Study of Different Formulations for the Multiperiod Blending Problem Applied to Lithium Recovery from Produced Water,” in Computer Aided Chemical Engineering. Elsevier, 2023, vol. 52, pp. 1861–1866.