(482g) Tightening Piecewise Mccormick Relaxations through Partition-Dependent Bounds for Non-Partitioned Variables

The simplest and most common type of nonlinear constraint in Chemical Engineering arises when mixing multicomponent streams of different properties. Blending constraints appear in crude oil operations in refineries (Lee et al. 1996, Jia et al. 2003), in the blending of liquid fuels (Jia and Ierapetritou 2003, Kolodziej et al. 2013b), in the design of distributed wastewater treatment systems (Galan and Grossmann 1998, Meyer and Floudas 2006, Teles et al. 2012) and integrated water networks (Karuppiah and Grossmann 2006, Faria and Bagajewicz 2012, Rubio-Castro et al. 2013). Bilinear terms also arise in the trim loss problem in paper plants (Harjunkoski et al. 1998, Zorn and Sahinidis 2013). Bilinear terms are nonconvex and therefore give rise to a variety of local solutions that may be far from the global optimum.

In order to find rigorous global optimal solutions to bilinear problems, alternative algorithms can be used that have in common the generation of linear or mixed-integer linear relaxations of the original problem. A well-known example of an MILP relaxation is the piecewise McCormick envelopes of Grossmann and co-workers (Bergamini et al. 2005, Karuppiah and Grossmann 2006). While piecewise McCormick relaxation can prove global optimality for a typically large number of partitions, the resulting MILP problem quickly becomes intractable due to the linear growth of binary variables with the number of partitions (Kolodziej et al. 2013a). A tighter formulation using the same number of binary variables is thus needed.

Piecewise McCormick relaxation works by diving the domain of one of the variables in each bilinear term into a given number of partitions. A tighter relaxation, compared to the standard linear McCormick (1976) envelopes, results from considering partition-dependent lower and upper bounds for the partitioned variables. We now propose to use partition-dependent bounds also for the non-partitioned variables so as to further improve the quality of the relaxation. These can be determined through optimality-based bound contraction (see for instance Castro and Grossmann 2014), which involves solving two linear problems per partition and per variable. While hundreds or even thousands of linear bound contracting problems may be involved, the benefit from a tighter formulation more than compensates the additional computational time. Once the solution of the tightened relaxation is found, it is used as a starting point for solving the original nonlinear problem with a fast local solver, so as to find a near optimal solution and to compute a rigorous optimality gap.

The performance of the new algorithm is illustrated with a set of small test problems and larger water-using network design problems from the literature. For the latter, the results show that the proposed algorithm outperforms state-of-the-art commercial solvers BARON (Tawarmalani and Sahinidis 2005) and GloMIQO (Misener and Floudas 2013). This is an indication that piecewise relaxation schemes and optimality-based bound contraction should be used to a greater extent.

Acknowledgments: Financial support from the Luso-American Foundation under the 2013 Portugal-U.S. Research Networks program and from Fundação para a Ciência e Tecnologia through the Investigador FCT 2013 program.

References:

-Bergamini, M.L., Aguirre, P., Grossmann, I.E. (2005). Logic-based outer approximation for globally optimal synthesis of process networks. Computers and Chemical Engineering 29, 1914-1933.

-Castro, P.M., Grossmann, I.E. (2014). Optimality-based Bound Contraction with Multiparametric Disaggregation for the Global Optimization of Mixed-Integer Bilinear Problems. Journal of Global Optimization. Doi: 10.1007/s10898-014-0162-6.

-Faria, D.C., Bagajewicz, M.J. (2012). A New Approach for Global Optimization of a Class of MINLP Problems with Applications to Water Management and Pooling Problems. AIChE J. 58 (8) 2320-2335.

-Galan, B., Grossmann, I.E. (1998). Optimal Design of Distributed Wastewater Treatment Networks. Ind. Eng. Chem. Res. 37, 4036.

-Harjunkoski, I., Westerlund, T., Pörn, R., Skrifvars, H. (1998). Different Transformations for Solving Non-convex Trim Loss Problems by MINLP. European Journal of Operational Research, 105, 594-603.

-Jia, Z., Ierapetritou, M. (2003). Mixed-Integer Linear Programming Model for Gasoline Blending and Distribution Scheduling. Ind. Eng. Chem. Res. 42, 825-835.

-Jia, Z., Ierapetritou, M., Kelly, J.D. (2003). Refinery Short-term Scheduling Using Continuous Time Formulation: Crude-Oil Operations. Ind. Eng. Chem. Res. 42, 3085-3097.

-Karuppiah, R., Grossmann, I.E. (2006). Global optimization for the synthesis of integrated water systems in chemical processes. Computers and Chemical Engineering 30, 650-673.

-Kolodziej, S., Castro P.M., Grossmann, I.E. (2013a). Global Optimization of Bilinear Programs with a Multiparametric Disaggregation Technique. Journal of Global Optimization 57, 1039-1063.

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

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

-McCormick, G.P. (1976). Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Mathematical Programming 10, 146.

-Meyer, C.A., Floudas, C.A. (2006). Global Optimization of a Combinatorially Complex Generalized Pooling Problem. AIChE J. 52 (3), 1027.

-Misener, R., Floudas, C.A. (2013b). GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization 57, 3-50.

-Rubio-Castro, E., Ponce-Ortega, J.M., Serna-González, M., El-Halwagi, M.M., Pham, V. (2013). Global Optimization in Property-based Inter-plant Water Integration. AIChE J. 59 (3), 813-833.

-Tawarmalani, M., Sahinidis, N.V. (2005). A polyhedral branch-and-cut approach to global optimization. Mathematical Programming 103 (2), 225-249.

-Teles, J.P., Castro, P.M., Matos, H.A. (2012). Global Optimization of Water Networks Design using Multiparametric Disaggregation. Computers and Chemical Engineering 40, 132-147.

-Zorn, K., Sahinidis, N.V. (2013). Computational Experience with Applications of Bilinear Cutting Planes. Industrial & Engineering Chemistry Research, 52, 7514-7525.