×

Global optimization of MIQCPs with dynamic piecewise relaxations. (English) Zbl 1405.90084

Summary: We propose a new deterministic global optimization algorithm for solving mixed-integer bilinear programs. It relies on a two-stage decomposition strategy featuring mixed-integer linear programming relaxations to compute estimates of the global optimum, and constrained non-linear versions of the original non-convex mixed-integer nonlinear program to find feasible solutions. As an alternative to spatial branch-and-bound with bilinear envelopes, we use extensively piecewise relaxations for computing estimates and reducing variable domain through optimality-based bound tightening. The novelty is that the number of partitions, a critical tuning parameter affecting the quality of the relaxation and computational time, increases and decreases dynamically based on the computational requirements of the previous iteration. Specifically, the algorithm alternates between piecewise McCormick and normalized multiparametric disaggregation. When solving ten benchmark problems from the literature, we obtain the same or better optimality gaps than two commercial global optimization solvers.

MSC:

90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming

Software:

ANTIGONE; APOGEE; GloMIQO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Meyer, CA; Floudas, CA, Global optimization of a combinatorially complex generalized pooling problem, AIChE J., 52, 1027-1037, (2006) · doi:10.1002/aic.10717
[2] Misener, R; Thompson, JP; Floudas, CA, APOGEE: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes, Comput. Chem. Eng., 35, 876-892, (2011) · doi:10.1016/j.compchemeng.2011.01.026
[3] Castro, PM, New MINLP formulation for the multiperiod pooling problem, AIChE J., 61, 3728-3738, (2015) · doi:10.1002/aic.15018
[4] Lotero, I; Trespalacios, F; Grossmann, IE; Papageorgiou, DJ; Cheon, M-S, An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem, Comput. Chem. Eng., 87, 13-35, (2016) · doi:10.1016/j.compchemeng.2015.12.017
[5] Quesada, I; Grossmann, IE, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng., 19, 1219-1242, (1995) · doi:10.1016/0098-1354(94)00123-5
[6] Lee, S; Grossmann, IE, Global optimization of nonlinear generalized disjunctive programming with bilinear equality constraints: applications to process networks, Comput. Chem. Eng., 27, 1557-1575, (2003) · doi:10.1016/S0098-1354(03)00098-X
[7] Faria, DC; Bagajewicz, MJ, Novel bound contraction procedure for global optimization of bilinear MINLP problems with applications to water management problems, Comput. Chem. Eng., 35, 446-455, (2011) · doi:10.1016/j.compchemeng.2010.04.010
[8] Rubio-Castro, E; Ponce-Ortega, JM; Serna-González, M; El-Halwagi, MM; Pham, V, Global optimization in property-based interplant water integration, AIChE J., 59, 813-833, (2013) · doi:10.1002/aic.13874
[9] Alnouri, S; Linke, P; El-Halwagi, MM; Eden, MR (ed.); Siirola, JDS (ed.); Towler, GP (ed.), Spatially constrained interplant water network synthesis with water treatment options, 237-242, (2014), Amsterdam
[10] Teles, JP; Castro, PM; Matos, HA, Global optimization of water networks design using multiparametric disaggregation, Comput. Chem. Eng., 40, 132-147, (2012) · doi:10.1016/j.compchemeng.2012.02.018
[11] Koleva, M.N., Styan, C.A., Papageorgiou, L.G.: Optimisation approaches for the synthesis of water treatment plants. Comput. Chem. Eng. (2017)
[12] Andrade, T; Ribas, G; Oliveira, F, A strategy based on convex relaxation for solving the oil refinery operations planning problem, Ind. Eng. Chem. Res., 55, 144-155, (2016) · doi:10.1021/acs.iecr.5b01132
[13] Castillo Castillo, P; Castro, PM; Mahalec, V, Global optimization algorithm for large-scale refinery planning models with bilinear terms, Ind. Eng. Chem. Res., 56, 530-548, (2017) · doi:10.1021/acs.iecr.6b01350
[14] Castro, PM; Grossmann, IE, Global optimal scheduling of crude oil blending operations with RTN continuous-time and multiparametric disaggregation, Ind. Eng. Chem. Res., 53, 15127-15145, (2014) · doi:10.1021/ie503002k
[15] Cerdá, J; Pautasso, PC; Cafaro, DC, Efficient approach for scheduling crude oil operations in marine-access refineries, Ind. Eng. Chem. Res., 54, 8219-8238, (2015) · doi:10.1021/acs.iecr.5b01461
[16] Zhao, Y; Wu, N; Li, Z; Qu, T, A novel solution approach to a priority-slot-based continuous-time mixed integer nonlinear programming formulation for a crude-oil scheduling problem, Ind. Eng. Chem. Res., 55, 10955-10967, (2016) · doi:10.1021/acs.iecr.6b01046
[17] Catalão, JPS; Pousinho, HMI; Mendes, VMF, Hydro energy systems management in Portugal: profit-based evaluation of a mixed-integer nonlinear approach, Energy, 36, 500-507, (2011) · doi:10.1016/j.energy.2010.10.014
[18] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (2013) · Zbl 0704.90057
[19] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138, (1996) · Zbl 0856.90103 · doi:10.1007/BF00138689
[20] Smith, EMB; Pantelides, CC, Global optimisation of nonconvex minlps, Comput. Chem. Eng., 21, s791-s796, (1997) · doi:10.1016/S0098-1354(97)87599-0
[21] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[22] Karuppiah, R; Grossmann, IE, Global optimization for the synthesis of integrated water systems in chemical processes, Comput. Chem. Eng., 30, 650-673, (2006) · doi:10.1016/j.compchemeng.2005.11.005
[23] Alfaki, M; Haugland, D, A multi-commodity flow formulation for the generalized pooling problem, J. Glob. Optim., 56, 917-937, (2013) · Zbl 1272.90103 · doi:10.1007/s10898-012-9890-7
[24] Bergamini, ML; Aguirre, P; Grossmann, I, Logic-based outer approximation for globally optimal synthesis of process networks, Comput. Chem. Eng., 29, 1914-1933, (2005) · doi:10.1016/j.compchemeng.2005.04.003
[25] Wicaksono, DS; Karimi, IA, Piecewise MILP under- and overestimators for global optimization of bilinear programs, AIChE J., 54, 991-1008, (2008) · doi:10.1002/aic.11425
[26] Li, X; Chen, Y; Barton, PI, Nonconvex generalized benders decomposition with piecewise convex relaxations for global optimization of integrated process design and operation problems, Ind. Eng. Chem. Res., 51, 7287-7299, (2012) · doi:10.1021/ie201262f
[27] Castro, PM, Tightening piecewise mccormick relaxations for bilinear problems, Comput. Chem. Eng., 72, 300-311, (2015) · doi:10.1016/j.compchemeng.2014.03.025
[28] Kolodziej, S; Castro, PM; Grossmann, IE, Global optimization of bilinear programs with a multiparametric disaggregation technique, J. Glob. Optim., 57, 1039-1063, (2013) · Zbl 1282.90137 · doi:10.1007/s10898-012-0022-1
[29] Castro, PM, Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems, J. Glob. Optim., 64, 765-784, (2016) · Zbl 1346.90625 · doi:10.1007/s10898-015-0342-z
[30] Faria, DC; Bagajewicz, MJ, A new approach for global optimization of a class of MINLP problems with applications to water management and pooling problems, AIChE J., 58, 2320-2335, (2012) · doi:10.1002/aic.12754
[31] Castro, PM, Spatial branch-and-bound algorithm for MIQCPs featuring multiparametric disaggregation, Optim. Methods Softw., 32, 719-737, (2017) · Zbl 1379.90019 · doi:10.1080/10556788.2016.1264397
[32] Castro, PM; Teles, JP, Comparison of global optimization algorithms for the design of water-using networks, Comput. Chem. Eng., 52, 249-261, (2013) · doi:10.1016/j.compchemeng.2013.01.013
[33] Castro, PM; Grossmann, IE, Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems, J. Glob. Optim., 59, 277-306, (2014) · Zbl 1298.90058 · doi:10.1007/s10898-014-0162-6
[34] Nagarajan, H; Lu, M; Yamangil, E; Bent, R; Rueher, M (ed.), Tightening mccormick relaxations for nonlinear programs via dynamic multivariate partitioning, 369-387, (2016), Cham · doi:10.1007/978-3-319-44953-1_24
[35] Saxena, A; Bonami, P; Lee, J, Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations, Math. Program., 124, 383-411, (2010) · Zbl 1198.90330 · doi:10.1007/s10107-010-0371-9
[36] Saxena, A; Bonami, P; Lee, J, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Math. Program., 130, 359-413, (2011) · Zbl 1229.90144 · doi:10.1007/s10107-010-0340-3
[37] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[38] Misener, R; Floudas, CA, Glomiqo: global mixed-integer quadratic optimizer, J. Glob. Optim., 57, 3-50, (2013) · Zbl 1272.90034 · doi:10.1007/s10898-012-9874-7
[39] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2
[40] Gleixner, AM; Berthold, T; Müller, B; Weltge, S, Three enhancements for optimization-based bound tightening, J. Glob. Optim., 67, 731-757, (2017) · Zbl 1369.90106 · doi:10.1007/s10898-016-0450-4
[41] Balas, E, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Algebr. Discrete Methods, 6, 466-486, (1985) · Zbl 0592.90070 · doi:10.1137/0606047
[42] Atamturk, A; Nemhauser, GL; Savelsbergh, MWP, Conflict graphs in solving integer programming problems, Eur. J. Oper. Res., 121, 40-55, (2000) · Zbl 0959.90034 · doi:10.1016/S0377-2217(99)00015-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.