×

zbMATH — the first resource for mathematics

Optimality-based domain reduction for inequality-constrained NLP and MINLP problems. (English) Zbl 07203798
Summary: In spatial branch-and-bound algorithms, optimality-based domain reduction is normally performed after solving a node and relies on duality information to reduce ranges of variables. In this work, we propose novel optimality conditions for NLP and MINLP problems and apply them for domain reduction prior to solving a node in branch-and-bound. The conditions apply to nonconvex inequality-constrained problems for which we exploit monotonicity properties of objectives and constraints. We develop three separate reduction algorithms for unconstrained, one-constraint, and multi-constraint problems. We use the optimality conditions to reduce ranges of variables through forward and backward bound propagation of gradients respective to each decision variable. We describe an efficient implementation of these techniques in the branch-and-bound solver BARON. The implementation dynamically recognizes and ignores inactive constraints at each node of the search tree. Our computations demonstrate that the proposed techniques often reduce the solution time and total number of nodes for continuous problems; they are less effective for mixed-integer programs.
MSC:
90C30 Nonlinear programming
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Wunderling, R.; Jünger, M.; Reinelt, G., Mixed integer programming: analyzing 12 years of progress, Facets of Combinatorial Optimization, 449-481 (2013), Berlin: Springer, Berlin · Zbl 1317.90206
[2] Balakrishnan, V.; Boyd, S.; Leondes, CT, Global optimization in control system analysis and design, Control and Dynamic Systems, Advances in Theory and Applications (1992), New York: Academic Press, New York
[3] 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
[4] Bixby, R.; Rothberg, E., Progress in computational mixed integer programming-a look back from the other side of the tipping point, Ann. Oper. Res., 149, 37-41 (2007) · Zbl 1213.90011
[5] Bliek, C., Spellucci, P., Vicente, L. N., Neumaier, A., Granvilliers, L., Huens, E., Hentenryck, P., Sam-Haroud, D., Faltings, B.: Algorithms for solving nonlinear constrained and optimization problems: the state of the art (2001). https://www.mat.univie.ac.at/ neum/ms/StArt.pdf
[6] Brearley, AL; Mitra, G.; Williams, HP, Analysis of mathematical programming problems prior to applying the simplex algorithm, Math. Program., 8, 54-83 (1975) · Zbl 0317.90037
[7] Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib-A collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119 (2003) · Zbl 1238.90104
[8] 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)
[9] Cozad, A.; Sahinidis, NV, A global MINLP approach to symbolic regression, Math. Program., 170, 97-119 (2018) · Zbl 1402.90092
[10] 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)
[11] GLOBAL Library. http://www.gamsworld.org/global/globallib.htm
[12] Gondzio, J., Presolve analysis of linear programs prior to applying an interior point method, INFORMS J. Comput., 9, 73-91 (1997) · Zbl 0890.90143
[13] Grossmann, IE; Caballero, JA; Yeomans, H., Advances in mathematical programming for the synthesis of process systems, Lat. Am. Appl. Res., 30, 263-284 (2000)
[14] Harjunkoski, I.; Westerlund, T.; Pörn, R.; Skrifvars, H., Different transformations for solving non-convex trim-loss problems by MINLP, Eur. J. Oper. Res., 105, 594-603 (1998) · Zbl 0955.90095
[15] Heinz, S.; Schulz, J.; Beck, JC, Using dual presolving reductions to reformulate cumulative constraints, Constraints, 18, 166-201 (2013) · Zbl 1309.90066
[16] Hoffman, KL; Padberg, M., Improving LP-representations of zero-one linear programs for branch-and-cut, ORSA J. Comput., 3, 121-134 (1991) · Zbl 0755.90062
[17] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches (1996), Berlin: Springer, Berlin · Zbl 0867.90105
[18] Imbert, J.; Van Hentenryck, P., Redundancy elimination with a lexicographic solved form, Ann. Math. Artif. Intell., 17, 85-106 (1996) · Zbl 0887.90115
[19] Jezowski, J., Review of water network design methods with literature annotations, Ind. Eng. Chem. Res., 49, 4475-4516 (2010)
[20] Khajavirad, A.; Michalek, JJ; Sahinidis, NV, Relaxations of factorable functions with convex-transformable intermediates, Math. Program., 144, 107-140 (2014) · Zbl 1301.65047
[21] Khajavirad, A.; Sahinidis, NV, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput., 10, 383-421 (2018) · Zbl 1400.90227
[22] Lin, Y.; Schrage, L., The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668 (2009) · Zbl 1177.90325
[23] Mahajan, AI; Cochran, JJ; Cox, LA; Keskinocak, P.; Kharoufeh, JP; Smith, JC, Presolving mixed-integer linear programs, Wiley Encyclopedia of Operations Research and Management Science (2010), New York: Wiley, New York
[24] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I-convex underestimating problems, Math. Program., 10, 147-175 (1976) · Zbl 0349.90100
[25] McCormick, GP, Nonlinear Programming: Theory, Algorithms and Applications (1983), Hoboken: Wiley, Hoboken
[26] MINLP2 Library. http://www.minlplib.org
[27] Misener, R.; Floudas, ChA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526 (2014) · Zbl 1301.90063
[28] Mitsos, A.; Chachuat, B.; Barton, PI, Mccormick-based relaxations of algorithms, SIAM J. Optim., 20, 573-601 (2009) · Zbl 1192.65083
[29] Nemhauser, GL; Savelsbergh, MP; Sigismondi, GC, MINTO, a mixed INTeger optimizer, Oper. Res. Lett., 15, 47-58 (1994) · Zbl 0806.90095
[30] Neumaier, A., Molecular modeling of proteins and mathematical prediction of protein structure, SIAM Rev., 39, 407-460 (1997) · Zbl 0939.92013
[31] Princeton Library. http://www.gamsworld.org/performance/princetonlib/princetonlib.htm
[32] Puranik, Y.; Sahinidis, NV, Bounds tightening based on optimality conditions for nonconvex box-constrained optimization, J. Glob. Optim., 67, 59-77 (2017) · Zbl 1359.90107
[33] Puranik, Y.; Sahinidis, NV, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22, 338-376 (2017) · Zbl 1387.90164
[34] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566 (1995)
[35] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-139 (1996)
[36] Sahinidis, Nikolaos V., Global Optimization and Constraint Satisfaction: The Branch-and-Reduce Approach, Global Optimization and Constraint Satisfaction, 1-16 (2003), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1255.90102
[37] Sahinidis, NV, Mixed-integer nonlinear programming 2018, Optim. Eng., 20, 301-306 (2019)
[38] Savelsbergh, MWP, Preprocessing and probing for mixed integer programming problems, ORSA J. Comput., 6, 445-454 (1994) · Zbl 0814.90093
[39] Schichl, H.; Neumaier, A., Interval analysis on directed acyclic graphs for global optimization, J. Glob. Optim., 33, 541-562 (2005) · Zbl 1094.65061
[40] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36 (1998) · Zbl 0906.90159
[41] Sherali, HD; Wang, H., Global optimization of nonconvex factorable programming problems, Math. Program., 89, 459-478 (2001) · Zbl 0985.90073
[42] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591 (2004) · Zbl 1062.90041
[43] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[44] Van Roy, TJ; Wolsey, LA, Solving mixed integer programming problems using automatic reformulation, Oper. Res., 35, 45-57 (1987) · Zbl 0614.90082
[45] Vigerske, S.; Gleixner, A., SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Optim. Methods Softw., 33, 3, 563-593 (2018) · Zbl 1398.90112
[46] Vigerske, S.: Decomposition of multistage stochastic programs and a constraint integer programming approach to mixed-integer nonlinear programming. PhD thesis, Humboldt Universität zu Berlin (2013)
[47] Wilson, ZT; Sahinidis, NV, The ALAMO approach to machine learning, Comput. Chem. Eng., 106, 785-795 (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.