(514a) Global Optimization Algorithm for Miqcps Featuring Spatial Branch-and-Bound and Multiparametric Disaggregation

Mixed-integer quadratic constrained problems (MIQCPs) can be found in Process Systems Engineering when dealing with design and operational problems. Examples involve water networks [1-2], blending in petroleum refineries [3-9] and hydroelectric power plants [10]. Due to their non-convex nature, MIQCPs are often very difficult to solve to global optimality and sometimes it is already challenging to find a feasible solution. It is thus not surprising that our community has focused on the development of commercial global optimization solvers such as BARON [11] and ANTIGONE [12], which have improved dramatically over the years and can now effectively tackle small to medium sized problems.

A key element for global optimization is the computation of a tight lower bound. Three different strategies can essentially be used to achieve this goal: (i) find an equivalent formulation that differs for the better in the quality of the relaxation (perhaps the pooling problem is the most well-known [13]); (ii) rely on piecewise relaxation approaches [14-20], of which multiparametric disaggregation [19-20] has the advantage of adding a number of binary variables that scales logarithmically with the number of partitions (N) that is translated into a significantly better computational performance for Nâ?¥10; (iii) instead of reducing the variables domain simultaneously, do it one by one, an iterative procedure known as spatial branch-and-bound (SB&B) that can converge rather slowly.

The main novelty of this work is to integrate SB&B with the powerful mixed-integer linear programming relaxation derived from normalized multiparametric disaggregation [20]. Experiments are conducted after selecting one variable to discretize in every bilinear term and using two alternative settings for the number of partitions: N=10 and N=100. Optimality based bound tightening (OBBT) with the standard McCormick relaxation [21] is also performed at every node of the tree, after bisecting the domain of the variable contributing to the largest discrepancy, so as to compute tight lower and upper bounds for all bilinearly appearing variables.

Through the solution of a set of 43 NLP and MINLP benchmark problems from the literature, we show that the proposed global optimization algorithm achieves a better performance in terms of optimality gap compared to BARON 14.0.3 and GloMIQO 2.3 [22], being N=10 the best alternative. This is an indication that both piecewise relaxation approaches and OBBT should be used to a greater extent. On the other hand, GloMIQO led to the lowest computational time, benefiting from the faster solution time in the easiest problems, while BARON had some difficulties in the process network problems but excelled with the MINLP multiperiod blending problems. The latter result is an indication that we should explore branching on the binary variables in future work.

Acknowledgments: Financial support from Fundação para a Ciência e Tecnologia (FCT) through the Investigador FCT 2013 program and project UID/MAT/04561/2013.

References:

[1] D.C. Faria, M.J. Bagajewicz, Novel bound contracting procedure for global optimization of bilinear MINLP problems with applications to water management problems. Comput. Chem. Eng. 35 (2011), pp. 446â??55.

[2] J.P. Teles, P.M. Castro, H.A. Matos, Global optimization of water networks design using multiparametric disaggregation. Comput. Chem. Eng. 40 (2012), pp. 132â??147.

[3] H. Lee, J.M. Pinto, I.E. Grossmann, S. Park, Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Ind. Eng. Chem. Res. 35 (1996), pp. 1630â??41.

[4] Jia Z., Ierapetritou, M., Kelly, J.D.: Refinery short-term scheduling using continuous time formulation: crude-oil operations. Ind Eng Chem Res 42, 3085â??97 (2003).

[5] P.M. Castro, I.E. Grossmann, Global optimal scheduling of crude oil blending operations with RTN Continuous-time and Multiparametric Disaggregation. Ind. Eng. Chem. Res. 53 (2014), pp. 15127-15145.

[6] C.A. Meyer, C.A. Floudas, Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(2) (2006), pp. 1027-1037.

[7] S.P. Kolodziej, I.E. Grossmann, K.C. Furman, N.W. Sawaya, A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput. Chem. Eng. 53 (2013), pp. 122â??142.

[8] P. Castro. New MINLP Formulation for the Multiperiod Pooling Problem. AIChE J. 61 (2015), pp. 3728-3738.

[9] I. Lotero, F. Trespalacios, M.-S. Cheon, D.J. Papageorgiou, I.E. Grossmann, An MILP- MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem. Comput. Chem. Eng. 87 (2016), pp. 13-35.

[10] P.M. Castro and I.E. Grossmann, Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems. J. Global Optim. 59 (2014), pp. 277-306.

[11] M. Tawarmalani, N.V. Sahinidis, A polyhedral branch-and-cut approach to global optimization. Math Program. 103(2) (2005), pp. 225â??49.

[12] R. Misener, C.A. Floudas, ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. J. Glob. Optim. 59 (2014), pp. 503-526.

[13] N. Boland, T. Kalinowski, F. Rigterink, New multi-commodity flow formulations for the pooling problem. J. Global Optim. DOI 10.1007/s10898-016-0404-x.

[14] M.L. Bergamini, P. Aguirre, I.E. Grossmann, Logic-based outer approximation for globally optimalâ?¨synthesis of process networks. Comput. Chem. Eng. 29 (2005), pp. 1914â??1933.

[15] D.N. Wicaksono, I.A. Karimi, Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J. 54 (2008), pp. 991-1008.

[16] C.E. Gounaris, R. Misener, C.A. Floudas, Computational comparison of piecewise-linear relaxations for pooling problems. Ind. Eng. Chem. Res. 48 (2009), pp. 5742-5766.

[17] M.M.F. Hasan, I.A. Karimi, Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J. 56 (2010), pp. 1880-1893.

[18] P.M. Castro, Tightening piecewise McCormick relaxations for bilinear problems. Comput. Chem. Eng. 72 (2015), pp. 300-311.

[19] S. Kolodziej, P.M. Castro and I.E. Grossmann, Global Optimization of Bilinear Programs with a Multiparametric Disaggregation Technique. J. Global Optim. 57 (2013), pp. 1039-1063.

[20] P.M. Castro, Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems. J. Global Optim. Doi: 10.1007/s10898-015-0342-z.

[21] G.P. McCormick, Computability of global solutions to factorable nonconvex programs. Part I. Convex â?¨underestimating problems. Math. Program. 10 (1976), pp. 147-175.

[22] R. Misener, C.A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 53 (2013), pp. 3â??50.