×

zbMATH — the first resource for mathematics

An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. (English) Zbl 1429.90056
Summary: In this work, we develop an adaptive, multivariate partitioning algorithm for solving nonconvex, mixed integer nonlinear programs (MINLPs) with polynomial functions to global optimality. In particular, we present an iterative algorithm that exploits piecewise, convex relaxation approaches via disjunctive formulations to solve MINLPs that is different than conventional spatial branch-and-bound approaches. The algorithm partitions the domains of variables in an adaptive and non-uniform manner at every iteration to focus on productive areas of the search space. Furthermore, domain reduction techniques based on sequential, optimization-based bound-tightening and piecewise relaxation techniques, as a part of a presolve step, are integrated into the main algorithm. Finally, we demonstrate the effectiveness of the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare our algorithm with state-of-the-art global optimization solvers. With our novel approach, we solve several large-scale instances, some of which are not solvable by state-of-the-art solvers. We also succeed in reducing the best known optimality gap for a hard, generalized pooling problem instance.

MSC:
90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Achterberg, T., SCIP: solving constraint integer programs, Math. Progr. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Al-Khayyal, FA; Falk, JE, Jointly constrained biconvex programming, Math. Oper. Res., 8, 273-286, (1983) · Zbl 0521.90087
[3] Belotti, P., Bound reduction using pairs of linear inequalities, J. Glob. Optim., 56, 787-819, (2013) · Zbl 1272.90033
[4] Belotti, P., Cafieri, S., Lee, J., Liberti, L.: On feasibility based bounds tightening (2012). https://hal.archives-ouvertes.fr/file/index/docid/935464/filename/377.pdf · Zbl 1311.90189
[5] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[6] Bent, R., Nagarajan, H., Sundar, K., Wang, S., Hijazi, H.: A polyhedral outer-approximation, dynamic-discretization optimization solver, 1.x. Tech. rep., Los Alamos National Laboratory, Los Alamos, NM, USA (2017). https://github.com/lanl-ansi/POD.jl
[7] Bergamini, ML; Grossmann, I.; Scenna, N.; Aguirre, P., An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms, Comput. Chem. Eng., 32, 477-493, (2008)
[8] Boukouvala, F.; Misener, R.; Floudas, CA, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Eur. J. Oper. Res., 252, 701-727, (2016) · Zbl 1346.90677
[9] Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib – a collection of test models for mixed-integer nonlinear programming, Inf. J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[10] Cafieri, S.; Lee, J.; Liberti, L., On convex relaxations of quadrilinear terms, J. Glob. Optim., 47, 661-685, (2010) · Zbl 1202.90236
[11] Castro, PM, Normalized multiparametric disaggregation: An efficient relaxation for mixed-integer bilinear problems, J. Glob. Optim., 64, 765-784, (2016) · Zbl 1346.90625
[12] Castro, PM, Tightening piecewise McCormick relaxations for bilinear problems, Comput. Chem. Eng., 72, 300-311, (2015)
[13] Coffrin, C., Hijazi, H.L., Van Hentenryck, P.: Strengthening convex relaxations with bound tightening for power network optimization. In: Principles and Practice of Constraint Programming, pp. 39-57. Springer, Berlin (2015)
[14] Dunning, I.; Huchette, J.; Lubin, M., JuMP: A modeling language for mathematical optimization, SIAM Rev., 59, 295-320, (2017) · Zbl 1368.90002
[15] D’Ambrosio, C.; Lodi, A.; Martello, S., Piecewise linear approximation of functions of two variables in milp models, Oper. Res. Lett., 38, 39-46, (2010) · Zbl 1182.90064
[16] 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)
[17] 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)
[18] Grossmann, IE; Trespalacios, F., Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming, AIChE J., 59, 3276-3295, (2013)
[19] Hasan, M.; Karimi, I., Piecewise linear relaxation of bilinear programs using bivariate partitioning, AIChE J., 56, 1880-1893, (2010)
[20] Hijazi, H.; Coffrin, C.; Hentenryck, P., Convex quadratic relaxations for mixed-integer nonlinear programs in power systems, Math. Progr. Comput., 9, 321-367, (2017) · Zbl 1387.90158
[21] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, J. Optim. Theory Appl., 30, 127-129, (1980) · Zbl 0393.90072
[22] Horst, R., Pardalos, P.M.: Handbook of global optimization, vol. 2. Springer, Berlin (2013) · Zbl 0805.00009
[23] Horst, R., Tuy, H.: Global optimization: deterministic approaches. Springer, Berlin (2013) · Zbl 0704.90057
[24] Karuppiah, R.; Grossmann, IE, Global optimization for the synthesis of integrated water systems in chemical processes, Comput. Chem. Eng., 30, 650-673, (2006)
[25] Kocuk, B.; Dey, SS; Sun, XA, Strong SOCP relaxations for the optimal power flow problem, Oper. Res., 64, 1177-1196, (2016) · Zbl 1354.90154
[26] Kolodziej, SP; Grossmann, IE; Furman, KC; Sawaya, NW, A discretization-based approach for the optimization of the multiperiod blend scheduling problem, Comput. Chem. Eng., 53, 122-142, (2013)
[27] Li, HL; Huang, YH; Fang, SC, A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems, Inf. J. Comput., 25, 643-653, (2012)
[28] Liberti, L.; Lavor, C.; Maculan, N., A branch-and-prune algorithm for the molecular distance geometry problem, Int. Trans. Oper. Res., 15, 1-17, (2008) · Zbl 1136.92037
[29] Lu, M., Nagarajan, H., Bent, R., Eksioglu, S., Mason, S.: Tight piecewise convex relaxations for global optimization of optimal power flow. In: Power Systems Computation Conference (PSCC), pp. 1-7. IEEE (2018)
[30] Lu, M.; Nagarajan, H.; Yamangil, E.; Bent, R.; Backhaus, S.; Barnes, A., Optimal transmission line switching under geomagnetic disturbances, IEEE Trans. Power Syst., 33, 2539-2550, (2018)
[31] Luedtke, J.; Namazifar, M.; Linderoth, J., Some results on the strength of relaxations of multilinear functions, Math. Progr., 136, 325-351, (2012) · Zbl 1286.90117
[32] McCormick, GP, Computability of global solutions to factorable nonconvex programs: Part i – convex underestimating problems, Math. Progr., 10, 147-175, (1976) · Zbl 0349.90100
[33] Meyer, CA; Floudas, CA, Global optimization of a combinatorially complex generalized pooling problem, AIChE J., 52, 1027-1037, (2006)
[34] Misener, R., Floudas, C.: Generalized pooling problem (2011). Available from Cyber-Infrastructure for MINLP [www.minlp.org, a collaboration of Carnegie Mellon University and IBM Research] at: www.minlp.org/library/problem/index.php?i=123
[35] Misener, R.; Floudas, CA, GloMIQO: Global mixed-integer quadratic optimizer, J. Glob. Optim., 57, 3-50, (2013) · Zbl 1272.90034
[36] 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)
[37] Mouret, S., Grossmann, I.E., Pestiaux, P.: Tightening the linear relaxation of a mixed integer nonlinear program using constraint programming. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pp. 208-222. Springer, Berlin (2009) · Zbl 1241.90054
[38] Nagarajan, H., Lu, M., Yamangil, E., Bent, R.: Tightening McCormick relaxations for nonlinear programs via dynamic multivariate partitioning. In: International Conference on Principles and Practice of Constraint Programming, pp. 369-387. Springer, Berlin (2016)
[39] Nagarajan, H., Pagilla, P., Darbha, S., Bent, R., Khargonekar, P.: Optimal configurations to minimize disturbance propagation in manufacturing networks. In: American Control Conference (ACC), 2017, pp. 2213-2218. IEEE (2017)
[40] Nagarajan, H., Sundar, K., Hijazi, H., Bent, R.: Convex hull formulations for mixed-integer multilinear functions. In: Proceedings of the XIV International Global Optimization Workshop (LEGO 18) (2018)
[41] Nagarajan, H., Yamangil, E., Bent, R., Van Hentenryck, P., Backhaus, S.: Optimal resilient transmission grid design. In: Power Systems Computation Conference (PSCC), 2016, pp. 1-7. IEEE (2016)
[42] Puranik, Y.; Sahinidis, NV, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22, 338-376, (2017) · Zbl 1387.90164
[43] Rikun, AD, A convex envelope formula for multilinear functions, J. Glob. Optim., 10, 425-437, (1997) · Zbl 0881.90099
[44] Ruiz, JP; Grossmann, IE, Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques, J. Glob. Optim., 67, 43-58, (2017) · Zbl 1359.90108
[45] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex nlps and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566, (1995)
[46] Ryoo, HS; Sahinidis, NV, Analysis of bounds for multilinear functions, J. Glob. Optim., 19, 403-424, (2001) · Zbl 0982.90054
[47] Sahinidis, NV, Baron: A general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[48] Speakman, E.E.: Volumetric Guidance for Handling Triple Products in Spatial Branch-and-Bound by. Ph.D. thesis, University of Michigan (2017)
[49] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[50] Teles, JP; Castro, PM; Matos, HA, Univariate parameterization for global optimization of mixed-integer polynomial problems, Eur. J. Oper. Res., 229, 613-625, (2013) · Zbl 1317.90213
[51] Trespalacios, F.; Grossmann, IE, Cutting plane algorithm for convex generalized disjunctive programs, Inf. J. Comput., 28, 209-222, (2016) · Zbl 1343.90054
[52] Vielma, JP; Nemhauser, GL, Modeling disjunctive constraints with a logarithmic number of binary variables and constraints, Math. Progr., 128, 49-72, (2011) · Zbl 1218.90137
[53] Wicaksono, DS; Karimi, I., Piecewise MILP under-and overestimators for global optimization of bilinear programs, AIChE J., 54, 991-1008, (2008)
[54] Wu, F., Nagarajan, H., Zlotnik, A., Sioshansi, R., Rudkevich, A.: Adaptive convex relaxations for gas pipeline network optimization. In: American Control Conference (ACC), 2017, pp. 4710-4716. IEEE (2017)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.