(449a) Closing the Gap Between Multiparametric Disaggregation and Piecewise Mccormick Relaxations for Miqcps

Multiparametric disaggregation (MDT) [1-2] is a technique for generating a mixed-integer linear relaxation for mixed-integer quadratically constrained problems (MIQCPs), a special class of mixed-integer nonlinear problems (MINLPs). It works by discretizing the domain of one of the variables of each bilinear term up to a certain accuracy level and has been shown competitive [3-5] compared to commercial solvers. Two parameters are needed to define the accuracy level, which are dependent on the value of the variable’s upper bound.

Piecewise McCormick (PCM) [6-11] is a closely related albeit conceptually different approach that partitions the domain of the variables, typically using uniform partitioning and a common setting for all variables. It can be viewed as a normalized approach in the sense that it is the range between a variable’s lower and upper bounds that is being partitioned. This is more convenient in the context of spatial branch-and-bound with frequent domain reduction, since consistently shorter partitions will be generated while keeping the number of partitions constraint. In contrast, MDT may require fewer discrete points due to the reduced domain but the location of those still required will be exactly the same. In other words, with PCM we potentially have a double impact in relaxation quality while keeping the problem size constant (the first impact is from tighter variable bounds) whereas in MDT we have a smaller impact but with a reduced size. Since the ultimate goal is to prove global optimality, the former strategy is preferable.

In this work, we bring multiparametric disaggregation closer to piecewise McCormick by considering a dimensionless domain for the discretized variables. More specifically, we now discretize the range [0,1] between a variable’s lower and upper bounds. Three advantages result: (i) a single parameter will be required to set the accuracy level; (ii) the same importance can be given for all discretized variables using a common accuracy parameter; (iii) this parameter can be directly related to the number of partitions of PCM, allowing for a direct comparison regardless of the problem data. While doing so, we keep MDT’s most important feature of scaling logarithmically with the number of partitions, rather than linearly as is the case for PCM.

Through the solution of 43 benchmark problems from the literature: 18 water-using network and 20 distributed wastewater treatment network design problems (NLP) [12], 7 multiperiod blending problems (MINLP) [13] and 3 hydroelectric scheduling problems (MINLP) [5,14]; we show that the computational performance of the new approach is already better than PCM for ten partitions, with the difference quickly rising for every ten-fold increase in the number of partitions. This is translated into an ability to generate optimality gaps that can be orders of magnitude lower. Furthermore, the quality of the relaxation is the same.

The MILP relaxation has also been used as the main element of a rigorous global optimization algorithm. It outperforms BARON 14.0 [15] and GloMIQO 2.3 [16] for these benchmark problems, clearly indicating that multiparametric disaggregation should be used to a greater extent.

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] Teles, J.P., Castro, P.M., Matos, H.A.: Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Global Optim. 55, 227-251 (2013)

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

[3] Castro, P.M., Teles, J.P.: Comparison of global optimization algorithms for the design of water-using networks. Comput. Chem. Eng. 52, 249–261 (2013) 


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

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

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


[7] Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in 
 chemical processes. Comput. Chem. Eng. 30, 650–673 (2006) 


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

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

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

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

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

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


[14] Catalão, J.P.S., Pousinho, H.M.I., Mendes, V.M.F.: Hydro energy systems management in Portugal: profit-based evaluation of a mixed-integer nonlinear approach. Energy 36, 500–507 (2011)

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

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