×

zbMATH — the first resource for mathematics

Domain reduction techniques for global NLP and MINLP optimization. (English) Zbl 1387.90164
Summary: Optimization solvers routinely utilize presolve techniques, including model simplification, reformulation and domain reduction techniques. Domain reduction techniques are especially important in speeding up convergence to the global optimum for challenging nonconvex nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) optimization problems. In this work, we survey the various techniques used for domain reduction of NLP and MINLP optimization problems. We also present a computational analysis of the impact of these techniques on the performance of various widely available global solvers on a collection of 1740 test problems.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T, Conflict analysis in mixed integer programming, Discrete Optimization, 4, 4-20, (2007) · Zbl 1169.90414
[2] Achterberg, T. (2009). Constraint Integer Programming. Berlin: Ph.D. thesis, Technische Universität. · Zbl 1171.90476
[3] Achterberg, T, SCIP: solving constraint integer programs, Mathematical Programming Computation, 1, 1-41, (2009) · Zbl 1171.90476
[4] Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., & Weninger, D. (2014). Multi-row presolve reductions in mixed integer programming. In Proceedings of the Twenty-Sixth RAMP Symposium. Hosei University, Tokyo. · Zbl 1185.90191
[5] Achterberg, T., Sabharwal, A., & Samulowitz, H. (2013). Stronger inference through implied literals from conflicts and knapsack covers. In Gomes, C., & Sellmann, M. (Eds.) Proceedings of 10th International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 1-11). Berlin: Springer. · Zbl 1382.68218
[6] Achterberg, T., & Wunderling, R. (2013). Mixed integer programming: Analyzing 12 years of progress. In Jünger, M., & Reinelt, G. (Eds.) Facets of Combinatorial Optimization (pp. 449-481). Berlin: Springer. · Zbl 1317.90206
[7] AIMMS: AIMMS Modeling Language (2015). http://www.aimms.com/.
[8] Al-Khayyal, FA; Sherali, HD, On finitely terminating branch-and-bound algorithms for some global optimization problems, SIAM Journal on Optimization, 10, 1049-1057, (2000) · Zbl 0994.65068
[9] Amaran, S; Sahinidis, NV, Global optimization of nonlinear least-squares problems by branch-and-bound and optimality constraints, TOP, 20, 154-172, (2012) · Zbl 1258.93102
[10] Amarger, RJ; Biegler, LT; Grossmann, IE, An automated modelling and reformulation system for design optimization, Computers & Chemical Engineering, 16, 623-636, (1992)
[11] AMPL: AMPL Modeling Language. http://www.ampl.com/. · Zbl 1348.90009
[12] Andersen, DE; Andersen, KD, Presolving in linear programming, Mathematical Programming, 71, 221-245, (1995) · Zbl 0846.90068
[13] Andersen, K; Pochet, Y, Coefficient strengthening: A tool for reformulating mixed-integer programs, Mathematical programming, 122, 121-154, (2010) · Zbl 1184.90111
[14] Apt, KR, The essence of constraint propagation, Theoretical computer science, 221, 179-210, (1999) · Zbl 0930.68164
[15] Araya, I., & Reyes, V. (2015). Interval Branch-and-Bound algorithms for optimization and constraint satisfaction: A survey and prospects. Journal of Global Optimization, 1-30. · Zbl 1353.90113
[16] Araya, I; Soto, R; Crawford, B, Adaptive filtering strategy for numerical constraint satisfaction problems, Expert Systems with Applications, 42, 8086-8094, (2015)
[17] Atamtürk, A; Nemhauser, GL; Savelsbergh, MWP, Conflict graphs in solving integer programming problems, European Journal of Operational Research, 121, 40-55, (2000) · Zbl 0959.90034
[18] Balakrishnan, V., & Boyd, S. (1992). Global optimization in control system analysis and design. In Leondes, C.T. (Ed.) Control and Dynamic Systems, Advances in Theory and Applications. New York: Academic Press. · Zbl 0795.93040
[19] Bao, X; Khajavirad, A; Sahinidis, NV; Tawarmalani, M, Global optimization of nonconvex problems with multilinear intermediates, Mathematical Programming Computation, 7, 1-37, (2015) · Zbl 1317.90243
[20] Bao, X; Sahinidis, NV; Tawarmalani, M, Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optimization Methods and Software, 24, 485-504, (2009) · Zbl 1179.90252
[21] BARON. http://minlp.com/baron.
[22] Belotti, P, Bound reduction using pairs of linear inequalities, Journal of Global Optimization, 56, 787-819, (2013) · Zbl 1272.90033
[23] Belotti, P., Cafieri, S., Lee, J., & Liberti, L. (2010). Feasibility-based bounds tightening via fixed points. In Wu, W., & Daescu, O. (Eds.) Combinatorial Optimization and Applications (pp. 65-76). Berlin: Springer. · Zbl 1311.90189
[24] Belotti, P., Cafieri, S., Lee, J., & Liberti, L. (2012). On feasibility based bounds tightening. http://www.optimization-online.org/DB_HTML/2012/01/3325.html. · Zbl 1311.90189
[25] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optimization Methods and Software, 24, 597-634, (2009) · Zbl 1179.90237
[26] Benhamou, F., Goualard, F., Granvilliers, L., & Puget, J. (1999). Revising hull and box consistency. In Proceedings of the 1999 International Conference on Logic Programming, pp. 230-244. Massachusetts Institute of Technology. · Zbl 0814.90093
[27] Benhamou, F., McAllester, D., & Hentenryck, P.V. (1994). CLP (intervals) revisited. In Bruynooghe, M. (Ed.) Proceedings of the 1994 International Symposium on Logic programming (pp. 124-138). Cambridge: MIT Press.
[28] Benhamou, F; Older, WJ, Applying interval arithmetic to real, integer, and Boolean constraints, The Journal of Logic Programming, 32, 1-24, (1997) · Zbl 0882.68032
[29] Bessiere, C. (2006). Walsh Constraint propagation. In Rossi, F., van, P., & Beek, T. (Eds.) Handbook of Constraint Programming, chap. 2 (pp. 29-83). Amsterdam: Elsevier. · Zbl 0614.90082
[30] Bessiere, C; Stergiou, K; Walsh, T, Domain filtering consistencies for non-binary constraints, Artificial Intelligence, 172, 800-822, (2008) · Zbl 1182.68218
[31] Bixby, R; Rothberg, E, Progress in computational mixed integer programming-a look back from the other side of the tipping point, Annals of Operations Research, 149, 37-41, (2007) · Zbl 1213.90011
[32] Bordeaux, L., Hamadi, Y., & Vardi, M.Y. (2007). An analysis of slow convergence in interval propagation. In Bessiere, C. (Ed.) Principles and Practice of Constraint Programming-CP 2007 (pp. 790-797). Berlin: Springer-Verlag. · Zbl 1145.68506
[33] Bordeaux, L; Katsirelos, G; Narodytska, N; Vardi, MY, The complexity of integer bound propagation, Journal of Artificial Intelligence Research, 40, 657-676, (2011) · Zbl 1216.68238
[34] Borradaile, G., & van Hentenryck, P. (2005). Safe and tight linear estimators for global optimization. Mathematical Programming, 102, 495-517. · Zbl 1066.90087
[35] Brearley, AL; Mitra, G; Williams, HP, Analysis of mathematical programming problems prior to applying the simplex algorithm, Mathematical programming, 8, 54-83, (1975) · Zbl 0317.90037
[36] Brooke, A., Kendrick, D., & Meeraus, A. (1988). GAMS-A User’s Guide. The Scientific Press, Redwood City CA. · Zbl 0939.92013
[37] Burer, S; Chen, J, Relaxing the optimality conditions of box QP, Computational Optimization and Applications, 48, 653-673, (2011) · Zbl 1242.90151
[38] Burer, S; Vandenbussche, D, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Mathematical Programming, 113, 259-282, (2008) · Zbl 1135.90034
[39] Burer, S; Vandenbussche, D, Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Computational Optimization and Applications, 43, 181-195, (2009) · Zbl 1170.90522
[40] Bussieck, MR; Drud, AS; Meeraus, A, Minlplib-A collection of test models for mixed-integer nonlinear programming, INFORMS Journal on Computing, 15, 114-119, (2003) · Zbl 1238.90104
[41] Caprara, A; Locatelli, M, Global optimization problems and domain reduction strategies, Mathematical Programming, 125, 123-137, (2010) · Zbl 1198.90325
[42] Caprara, A., Locatelli, M., & Monaci, M. (2016). Theoretical and computational results about optiMality-based domain reductions. Computational Optimization and Applications, 1-21. · Zbl 1348.90525
[43] Castro, PM; Grossmann, IE, Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems, Journal of Global Optimization, 59, 277-306, (2014) · Zbl 1298.90058
[44] 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)
[45] Chen, J; Burer, S, Globally solving nonconvex quadratic programming problems via completely positive programming, Mathematical Programming Computation, 4, 33-52, (2012) · Zbl 1257.90065
[46] Chinneck, J.W. (2008). Feasibility and infeasibility in optimization. New York: Springer. · Zbl 1178.90369
[47] Cleary, JG, Logical arithmetic, Future computing systems, 2, 125-149, (1987)
[48] CMU-IBM open source MINLP project test set. http://egon.cheme.cmu.edu/ibm/page.htm. · Zbl 1181.90309
[49] Collavizza, H; Delobel, F; Rueher, M, Comparing partial consistencies, Reliable computing, 5, 213-228, (1999) · Zbl 1130.65310
[50] Cornelius, H; Lohner, R, Computing the range of values of real functions with accuracy higher than second order, Computing, 33, 331-347, (1984) · Zbl 0556.65037
[51] Crowder, H; Johnson, EL; Padberg, M, Solving large-scale zero-one linear programming problems, Operations Research, 31, 803-834, (1983) · Zbl 0576.90065
[52] Czyzyk, J; Mesnier, M; Moré, J, The NEOS server, IEEE Computational Science andamp; Engineering, 5, 68-75, (1998)
[53] D’Ambrosio, C; Lodi, A; Wiese, S; Bragalli, C, Mathematical programming techniques in water network optimization, European Journal of Operational Research, 243, 774-788, (2015) · Zbl 1346.90211
[54] Davis, E, Constraint propagation with interval labels, Artificial intelligence, 32, 281-331, (1987) · Zbl 0642.68176
[55] Domes, F; Neumaier, A, Constraint aggregation for rigorous global optimization, Mathematical Programming, 155, 375-401, (2016) · Zbl 1342.90142
[56] Du, K; Kearfott, RB, The cluster problem in multivariate global optimization, Journal of Global Optimization, 5, 253-265, (1994) · Zbl 0824.90121
[57] Edelkamp, S., & Schroedl, S. (2011). Heuristic search: Theory and applications Elsevier. · Zbl 1273.90165
[58] Falk, JE; Soland, RM, An algorithm for separable nonconvex programming problems, Management Science, 15, 550-569, (1969) · Zbl 0172.43802
[59] Faltings, B, Arc-consistency for continuous variables, Artificial intelligence, 65, 363-376, (1994) · Zbl 0803.68129
[60] Faria, DC; Bagajewicz, MJ, Global optimization of water management problems using linear relaxation and bound contraction methods, Industrial & Engineering Chemistry Research, 50, 3738-3753, (2011)
[61] Faria, DC; Bagajewicz, MJ, Novel bound contraction procedure for global optimization of bilinear MINLP problems with applications to water management problems, Computers & Chemical Engineering, 35, 446-455, (2011)
[62] 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 Journal, 58, 2320-2335, (2012)
[63] Ferris, M.C., & Munson, T.S. (2001). Preprocessing complementarity problems. In Ferris, M.C., Mangasarian, O.L., & Pang, J. (Eds.) Complementarity: Applications, Algorithms and Extensions (pp. 143-164). Dordrecht: Springer. · Zbl 0983.90063
[64] Fischetti, M; Salvagnin, D, Pruning moves, INFORMS Journal on Computing, 22, 108-119, (2010) · Zbl 1243.90136
[65] Fischetti, M; Toth, P, A new dominance procedure for combinatorial optimization problems, Operations Research Letters, 7, 181-187, (1988) · Zbl 0655.90064
[66] Focacci, F., Lodi, A., & Milano, M. (1999). Cost-based domain filtering. In Jaffar, J. (Ed.) Proceedings of Principles and Practice of Constraint Programming: 5th International Conference (pp. 189-203). Berlin: Springer. · Zbl 0955.90095
[67] Fourer, R., & Gay, D.M. (1994). Experience with a primal presolve algorithm. In Hager, W., Hearn, D., & Pardalos, P. (Eds.) Large Scale Optimization: State of the Art (pp. 135-154). Boston: Springer. · Zbl 0816.90101
[68] Fügenschuh, A., Homfeld, H., Schülldorf, H., & Vigerske, S. (2010). Mixed-integer nonlinear problems in transportation applications. In Proceedings of the 2nd International Conference on Engineering Optimization (CD-ROM) (p. 14). · Zbl 1297.49046
[69] Furman, KC; Sahinidis, NV, A critical review and annotated bibliography for heat exchanger network synthesis in the 20th century, Industrial & Engineering Chemistry Research, 41, 2335-2370, (2002)
[70] Gamrath, G; Koch, T; Martin, A; Miltenberger, M; Weninger, D, Progress in presolving for mixed integer programming, Mathematical Programming Computation, 7, 367-398, (2015) · Zbl 1329.90089
[71] Gleixner, A.M., Berthold, T., Müller, B., & Weltge, S. (2016). Three enhancements for optimization-based bound tightening. ZIB Report, 15-16. · Zbl 1369.90106
[72] Gleixner, A.M., & Weltge, S. (2013). Learning and propagating Lagrangian variable bounds for mixed-integer nonlinear programming. In Proceedings of 10th International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 355-361). Berlin: Springer. · Zbl 1382.90063
[73] GLOBAL Library. http://www.gamsworld.org/global/globallib.htm.
[74] Gondzio, J, Presolve analysis of linear programs prior to applying an interior point method, INFORMS Journal on Computing, 9, 73-91, (1997) · Zbl 0890.90143
[75] Gould, N; Toint, PL, Preprocessing for quadratic programming, Mathematical Programming, 100, 95-132, (2004) · Zbl 1146.90491
[76] Grossmann, I, Enterprise-wide optimization: A new frontier in process systems engineering, AIChE Journal, 51, 1846-1857, (2005)
[77] Grossmann, IE; Caballero, JA; Yeomans, H, Advances in mathematical programming for the synthesis of process systems, Latin American Applied Research, 30, 263-284, (2000)
[78] Guignard, M; Spielberg, K, Logical reduction methods in zero-one programming-minimal preferred variables, Operations Research, 29, 49-74, (1981) · Zbl 0452.90044
[79] Hager, GD, Solving large systems of nonlinear constraints with application to data modeling, Interval Computations, 3, 169-200, (1993) · Zbl 0829.65007
[80] Hamed, ASE; McCormick, GP, Calculation of bounds on variables satisfying nonlinear inequality constraints, Journal of Global Optimization, 3, 25-47, (1993) · Zbl 0845.90105
[81] Hansen, E.R. (1992). Global optimization using interval analysis. Pure and Applied Mathematics. · Zbl 0762.90069
[82] Hansen, P; Jaumard, B; Lu, SH, An analytic approach to global optimization, Mathematical Programming, 52, 227-254, (1991) · Zbl 0747.90091
[83] Hansen, P; Jaumard, B; Ruiz, M; Xiong, J, Global minimization of indefinite quadratic functions subject to box constraints, Naval Research Logistics (NRL), 40, 373-392, (1993) · Zbl 0782.90071
[84] Harjunkoski, I; Westerlund, T; Pörn, R; Skrifvars, H, Different transformations for solving non-convex trim-loss problems by MINLP, European Journal of Operational Research, 105, 594-603, (1998) · Zbl 0955.90095
[85] Harvey, W., & Schimpf, J. (2002). Bounds consistency techniques for long linear constraints. In Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems (pp. 39-46). · Zbl 1342.90142
[86] Heinz, S; Schulz, J; Beck, JC, Using dual presolving reductions to reformulate cumulative constraints, Constraints, 18, 166-201, (2013) · Zbl 1309.90066
[87] Hoffman, KL; Padberg, M, Improving LP-representations of zero-one linear programs for branch-and-cut, ORSA Journal on Computing, 3, 121-134, (1991) · Zbl 0755.90062
[88] Hooker, J.N. (2007). Integrated methods for optimization. New York: Springer Science & Business Media. · Zbl 1122.90002
[89] Horst, R., & Tuy, H. (1996). Global Optimization: Deterministic Approaches, 3rd edn. Berlin: Springer Verlag. · Zbl 0867.90105
[90] Hu, J; Mitchell, JE; Pang, J, An LPCC approach to nonconvex quadratic programs, Mathematical programming, 133, 243-277, (2012) · Zbl 1244.90177
[91] Hunting, M. (2011). A nonlinear presolve algorithm in AIMMS, An AIMMS white paper, Paragon Decision Technology, BV. · Zbl 1130.65310
[92] Ibaraki, T, The power of dominance relations in branch-and-bound algorithms, Journal of the ACM, 24, 264-279, (1977) · Zbl 0357.90043
[93] Imbert, J; Hentenryck, PV, Redundancy elimination with a lexicographic solved form, Annals of Mathematics and Artificial Intelligence, 17, 85-106, (1996) · Zbl 0887.90115
[94] Jezowski, J, Review of water network design methods with literature annotations, Industrial & Engineering Chemistry Research, 49, 4475-4516, (2010)
[95] Karush, W. (1939). Minima of functions of several variables with inequalities as side constraints. Chicago, IL: Master’s thesis, Department of Mathematics, University of Chicago.
[96] Katsirelos, G. (2008). Nogood processing in CSPs. Ph.D. thesis: University of Toronto.
[97] Kearfott, RB, Decomposition of arithmetic expressions to improve the behavior of interval iteration for nonlinear systems, Computing, 47, 169-191, (1991) · Zbl 0739.65049
[98] Kearfott, R.B. (1996). Rigorous Global Search: Continuous Problems, Nonconvex Optimization and Its Applications Vol. 13. Dordrecht: Kluwer Academic Publishers. · Zbl 0876.90082
[99] Kearfott R.B. (2009). GlobSol user guide. Optimization Methods and Software, 24, 687-708. · Zbl 1180.90314
[100] Kell, B., Sabharwal, A., & van Hoeve, W. (2015). BDD-guided clause generation. In Michel, L. (Ed.) Integration of AI and OR Techniques in Constraint Programming (pp. 215-230): Springer. · Zbl 1459.68191
[101] Khajavirad, A; Michalek, JJ; Sahinidis, NV, Relaxations of factorable functions with convex-transformable intermediates, Mathematical Programming, 144, 107-140, (2014) · Zbl 1301.65047
[102] Khajavirad, A; Sahinidis, NV, Convex envelopes of products of convex and component-wise concave functions, Journal of Global Optimization, 52, 391-409, (2011) · Zbl 1268.90052
[103] Khajavirad, A; Sahinidis, NV, Convex envelopes generated from finitely many compact convex sets, Mathematical Programming, 137, 371-408, (2013) · Zbl 1284.90055
[104] Kılınç, M., & Sahinidis, N.V. (2014). Solving MINLPs with BARON. Presented at MINLP Workshop, Pittsburgh http://http://minlp.cheme.cmu.edu/2014/papers/kilinc.pdf. · Zbl 1182.68218
[105] Kohler, WH; Steiglitz, K, Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems, Journal of the ACM, 21, 140-156, (1974) · Zbl 0279.68035
[106] Kuhn, H.W., & Tucker, A.W. (1951). Nonlinear programming. In Neyman, J. (Ed.) Proceedings ofthe Second Berkeley Symposium on Mathematical Statistics and Probability (pp. 481-492). Berkeley: University of California Press. · Zbl 0044.05903
[107] Kulisch, U.W. (2009). Complete interval arithmetic and its implementation on the computer. In Cuyt, A., Krämer, W., Luther, W., & Markstein, P. (Eds.) Numerical Validation in Current Hardware Architectures. Berlin: Springer. · Zbl 1272.90033
[108] Lamar, BW, An improved branch and bound algorithm for minimum concave cost network flow problems, Journal of Global Optimization, 3, 261-287, (1993) · Zbl 0781.90035
[109] Land, AH; Doig, AG, An automatic method for solving discrete programming problems, Econometrica, 28, 497-520, (1960) · Zbl 0101.37004
[110] Lebbah, Y, ICOS: A branch and bound based solver for rigorous global optimization, Optimization Methods and Software, 24, 709-726, (2009) · Zbl 1179.90265
[111] Lebbah, Y; Michel, C; Rueher, M, A rigorous global filtering algorithm for quadratic constraints, Constraints, 10, 47-65, (2005) · Zbl 1066.90090
[112] Lebbah, Y., Michel, C., & Rueher, M. (2007). Using constraint techniques for a safe and fast implementation of optiMality-based reduction. In Proceedings of the 2007 ACM symposium on Applied Computing (pp. 326-331).
[113] Lebbah, Y; Michel, C; Rueher, M; Daney, D; Merlet, JP, Efficient and safe global constraints for handling numerical constraint systems, SIAM Journal on Numerical Analysis, 42, 2076-2097, (2005) · Zbl 1082.65051
[114] Lecoutre, C; Sais, L; Tabary, S; Vidal, V, Recording and minimizing nogoods from restarts, Journal on Satisfiability Boolean Modeling and Computation, 1, 147-167, (2007) · Zbl 1144.68373
[115] Leo, K., & Tack, G. (2015). Multi-Pass High-Level Presolving. In Twenty-Fourth International Joint Conference on Artificial Intelligence. · Zbl 1184.90111
[116] Lhomme, O. (1993). Consistency techniques for numeric CSPs. In International Joint Conference on Artificial Intelligence, (Vol. 93 pp. 232-238). · Zbl 0824.90121
[117] Lin, Y; Schrage, L, The global solver in the LINDO API, Optimization Methods and Software, 24, 657-668, (2009) · Zbl 1177.90325
[118] Lodwick, WA, Constraint propagation, relational arithmetic in AI systems and mathematical programs, Annals of Operations Research, 21, 143-148, (1989) · Zbl 0705.90056
[119] Lodwick, WA, Preprocessing nonlinear constraints with applications to the pooling problem, ORSA Journal on Computing, 4, 119-131, (1992) · Zbl 0770.90067
[120] Lynce, I., & Marques-Silva, J. (2003). Probing-based preprocessing techniques for propositional satisfiability. In Proceedings of 15th ICTAI (pp. 105-110). · Zbl 1198.90325
[121] Mahajan, A. (2010). Presolving Mixed-Integer Linear Programs. In Cochran, J.J., Cox, L.A., Keskinocak, P., Kharoufeh, J.P., & Smith, J.C. (Eds.) Wiley Encyclopedia of Operations Research and Management Science. New York: Wiley · Zbl 1329.90089
[122] Mangasarian, OL; McLinden, L, Simple bounds for solutions of monotone complementarity problems and convex programs, Mathematical Programming, 32, 32-40, (1985) · Zbl 0567.90093
[123] Margot, F, Pruning by isomorphism in branch-and-cut, Mathematical Programming, 94, 71-90, (2002) · Zbl 1023.90088
[124] Margot, F, Exploiting orbits in symmetric ILP, Mathematical Programming, 98, 3-21, (2003) · Zbl 1082.90070
[125] Markót, MC; Schichl, H, Bound constrained interval global optimization in the COCONUT environment, Journal of Global Optimization, 60, 751-776, (2014) · Zbl 1302.90152
[126] Marques-Silva, JP; Sakallah, KA, GRASP: A search algorithm for propositional satisfiability, IEEE Transactions on Computers, 48, 506-521, (1999) · Zbl 1392.68388
[127] Martin, A. (2001). General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms. In Jünger, M., & Naddef, D.s (Eds.) Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions (pp. 1-25). Berlin: Springer. · Zbl 1052.90049
[128] Martin, A; Möller, M; Moritz, S, Mixed integer models for the stationary case of gas network optimization, Mathematical programming, 105, 563-582, (2006) · Zbl 1085.90035
[129] Martin, P., & Shmoys, D.B. (1996). A new approach to computing optimal schedules for the job-shop scheduling problem. In Cunningham, H.W., McCormick, T.S., & Queyranne, M. (Eds.) International Conference on Integer Programming and Combinatorial Optimization (pp. 389-403). Berlin: Springer. · Zbl 1011.90030
[130] Mayer, G, Epsilon-inflation in verification algorithms, Journal of Computational and Applied Mathematics, 60, 147-169, (1995) · Zbl 0839.65059
[131] McCormick, G.P. (1976). Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Mathematical Programming, 10, 147-175. · Zbl 0349.90100
[132] Messine, F, Deterministic global optimization using interval constraint propagation techniques, RAIRO-Operations Research, 38, 277-293, (2004) · Zbl 1114.90156
[133] Mészáros, CS; Suhl, UH, Advanced preprocessing techniques for linear and quadratic programming, OR Spectrum, 25, 575-595, (2003) · Zbl 1042.90031
[134] Meyer, CA; Floudas, CA, Convex envelopes for edge-concave functions, Mathematical programming, 103, 207-224, (2005) · Zbl 1099.90045
[135] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, Journal of Global Optimization, 59, 503-526, (2014) · Zbl 1301.90063
[136] Mittelmann, HD; Pruessner, A, A server for automated performance analysis of benchmarking data, Optimization Methods and Software, 21, 105-120, (2006) · Zbl 1181.90309
[137] Moore, R.E., Kearfott, R.B., & Cloud, M.J. (2009). Introduction to interval analysis. Siam Philadelphia. · Zbl 1168.65002
[138] Morrison, DR; Jacobson, SH; Sauppe, JJ; Sewell, EC, Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optimization, 19, 79-102, (2016) · Zbl 1387.90010
[139] Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., & Malik, S. (2001). Chaff: Engineering an efficient SAT solver. In Proceedings of the 38th annual Design Automation Conference, pp. 530-535. · Zbl 0881.90099
[140] Nannicini, G., Belotti, P., Lee, J., Linderoth, J., Margot, F., & Wächter, A. (2011). A probing algorithm for MINLP with failure prediction by SVM. In Achterberg, T., & Beck, J.C. (Eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 154-169). Berlin: Springer. · Zbl 1302.90160
[141] Nemhauser, GL; Savelsbergh, MP; Sigismondi, GC, MINTO, a mixed integer optimizer, Operations Research Letters, 15, 47-58, (1994) · Zbl 0806.90095
[142] Neumaier, A. (1990). Interval methods for systems of equations Cambridge university press. · Zbl 0715.65030
[143] Neumaier, A, Molecular modeling of proteins and mathematical prediction of protein structure, SIAM review, 39, 407-460, (1997) · Zbl 0939.92013
[144] Neumaier, A, Complete search in continuous global optimization and constraint satisfaction, Acta numerica, 13, 271-369, (2004) · Zbl 1113.90124
[145] Neumaier, A; Shcherbina, O, Safe bounds in linear and mixed-integer linear programming, Mathematical Programming, 99, 283-296, (2004) · Zbl 1098.90043
[146] Ostrowski, J; Linderoth, J; Rossi, F; Smriglio, S, Orbital branching, Mathematical Programming, 126, 147-178, (2011) · Zbl 1206.90101
[147] O’Sullivan, B. (2010). Automated Modelling and Solving in Constraint Programming. In Twenty-Fourth AAAI Conference on Artificial Intelligence. · Zbl 1085.90035
[148] Pardalos, PM; Chaovalitwongse, W; Iasemidis, LD; Sackellares, JC; Shiau, D; Carney, PR; Prokopyev, OA; Yatsenko, VA, Seizure warning algorithm based on optimization and nonlinear dynamics, Mathematical Programming, 101, 365-385, (2004) · Zbl 1055.92031
[149] Princeton Library. http://www.gamsworld.org/performance/princetonlib/princetonlib.htm. · Zbl 0781.90035
[150] Prosser, P., Stergiou, K., & Walsh, T. (2000). Singleton consistencies. In Dechter, R. (Ed.) Proceedings of 6th International Conference, CP 2000 Singapore (pp. 353-368). Berlin: Springer. · Zbl 1044.68790
[151] Puranik, Y., & Sahinidis, N.V. Bounds tightening on optimality conditions for nonconvex box-constrained optimization. Journal of Global Optimization. 10.1007/s10898-016-0491-8 · Zbl 1359.90107
[152] Puranik, Y., & Sahinidis, N.V. Deletion presolve for accelerating infeasibility diagnosis in optimization models. INFORMS Journal on Computing (in review). · Zbl 1297.49046
[153] Rajagopalan, S., & Sahinidis, N.V. (2017). The pooling problem. In Terlaky, T., Anjos, M., & Ahmed, S. (Eds.) Advances and Trends in Optimization with Engineering Applications, MOS-SIAM Book Series on Optimization. Philadelphia: SIAM. · Zbl 1137.90009
[154] Régin, J.C. (2011). Milano Global constraints: A survey. In Van, P., & Hentenryck, M. (Eds.) Hybrid optimization: The Ten Years of CPAIOR (pp. 63-134). New York: Springer. · Zbl 0906.90159
[155] Rikun, AD, A convex envelope formula for multilinear functions, Journal of Global Optimization, 10, 425-437, (1997) · Zbl 0881.90099
[156] Ríos-Mercado, RZ; Borraz-Sánchez, C, Optimization problems in natural gas transportation systems: A state-of-the-art review, Applied Energy, 147, 536-555, (2015)
[157] Roy, TJV; Wolsey, LA, Solving mixed integer programming problems using automatic reformulation, Operations Research, 35, 45-57, (1987) · Zbl 0614.90082
[158] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers & Chemical Engineering, 19, 551-566, (1995)
[159] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, Journal of Global Optimization, 8, 107-139, (1996) · Zbl 0856.90103
[160] Sahinidis, N.V. (2003). Global optimization and constraint satisfaction: The branch-and-reduce approach. In Bliek, C., Jermann, C., & Neumaier, A. (Eds.) Global Optimization and Constraint Satisfaction, Lecture Notes in Computer Science, (Vol. 2861 pp. 1-16). Berlin: Springer. · Zbl 1255.90102
[161] Sahinidis, NV; Tawarmalani, M, Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints, Journal of Global Optimization, 32, 259-280, (2005) · Zbl 1080.90087
[162] Sam-Haroud, D; Faltings, B, Consistency techniques for continuous constraints, Constraints, 1, 85-118, (1996)
[163] Sandholm, T., & Shields, R. (2006). Nogood learning for mixed integer programming. In Workshop on Hybrid Methods and Branching Rules in Combinatorial Optimization, Montréal (p. 138). · Zbl 0556.65037
[164] Savelsbergh, MWP, Preprocessing and probing for mixed integer programming problems, ORSA Journal on Computing, 6, 445-454, (1994) · Zbl 0814.90093
[165] Schichl, H; Markót, MC; Neumaier, A, Exclusion regions for optimization problems, Journal of Global Optimization, 59, 569-595, (2014) · Zbl 1297.65070
[166] Schichl, H; Neumaier, A, Exclusion regions for systems of equations, SIAM Journal on numerical analysis, 42, 383-408, (2004) · Zbl 1080.65041
[167] Schichl, H; Neumaier, A, Interval analysis on directed acyclic graphs for global optimization, Journal of Global Optimization, 33, 541-562, (2005) · Zbl 1094.65061
[168] Schichl, H; Neumaier, A, Transposition theorems and qualification-free optimality conditions, SIAM Journal on Optimization, 17, 1035-1055, (2006) · Zbl 1136.90043
[169] Schöbel, A; Scholz, D, The theoretical and empirical rate of convergence for geometric branch-and-bound methods, Journal of Global Optimization, 48, 473-495, (2010) · Zbl 1236.90148
[170] Scholkopf, B., & Smola, A.J. (2001). Learning with kernels: Support vector machines, regularization, optimization, and beyond. Cambridge: MIT press.
[171] Sellmann, M. (2004). Theoretical foundations of CP-based Lagrangian relaxation. In Wallace, M. (Ed.) Proceedings of 10th International Conference, CP 2004, Toronto, Canada (pp. 634-647). Berlin: Springer. · Zbl 1152.68584
[172] Sewell, EC; Sauppe, JJ; Morrison, DR; Jacobson, SH; Kao, GK, A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times, Journal of Global Optimization, 54, 791-812, (2012) · Zbl 1258.90043
[173] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, Journal of Global Optimization, 12, 1-36, (1998) · Zbl 0906.90159
[174] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal of Discrete Mathematics, 3, 411-430, (1990) · Zbl 0712.90050
[175] Sherali, HD; Adams, WP, A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, Discrete Applied Mathematics, 52, 83-106, (1994) · Zbl 0819.90064
[176] Sherali, H.D., & Adams, W.P. (1999). A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and its Applications Vol. 31. Dordrecht: Kluwer Academic Publishers. · Zbl 0926.90078
[177] Sinha, M; Achenie, LEK; Gani, R, Blanket wash solvent blend design using interval analysis, Industrial & Engineering Chemistry Research, 42, 516-527, (2003)
[178] Smith, A.B., & Sahinidis, N.V. (2009). Optimization techniques for phase retrieval based on single-crystal X-ray diffraction data. In Floudas, C.A., & Pardalos, P.M. (Eds.) Encyclopedia of Optimization (pp. 2858-2863). Boston: Springer. · Zbl 1329.90089
[179] Smith, E.M.B., & Pantelides, C.C. (1996). Global optimisation of general process models. In Grossmann, I.E. (Ed.) Global Optimization in Engineering Design (pp. 355-386). Boston: Kluwer Academic Publishers. · Zbl 0874.90199
[180] Stallman, RM; Sussman, GJ, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Artificial intelligence, 9, 135-196, (1977) · Zbl 0372.94024
[181] Stergiou, K, Heuristics for dynamically adapting propagation in constraint satisfaction problems, AI Communications, 22, 125-141, (2009) · Zbl 1185.90191
[182] Sturtevant, N.R., Felner, A., Likhachev, M., & Ruml, W. (2012). Heuristic search comes of age. In AAAI12: Proceedings of the 26th AAAI Conference on Artifical Intelligence.
[183] Tawarmalani, M; Richard, JP; Xiong, C, Explicit convex and concave envelopes through polyhedral subdivisions, Mathematical Programming, 138, 531-577, (2013) · Zbl 1273.90165
[184] Tawarmalani, M; Sahinidis, NV, Convex extensions and convex envelopes of l.s.c. functions, Mathematical Programming, 93, 247-263, (2002) · Zbl 1065.90062
[185] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99, 563-591, (2004) · Zbl 1062.90041
[186] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Mathematical Programming, 103, 225-249, (2005) · Zbl 1099.90047
[187] Thakur, LS, Domain contraction in nonlinear programming: minimizing a quadratic concave function over a polyhedron, Mathematics of Operations Research, 16, 390-407, (1990) · Zbl 0741.90068
[188] Thorsteinsson, ES; Ottosson, G, Linear relaxations and reduced-cost based propagation of continuous variable subscripts, Annals of operations research, 115, 15-29, (2002) · Zbl 1011.90030
[189] Tomlin, JA; Welch, JS, Formal optimization of some reduced linear programming problems, Mathematical programming, 27, 232-240, (1983) · Zbl 0535.90059
[190] Tomlin, LA; Welch, JS, Finding duplicate rows in a linear programming model, Operations Research Letters, 5, 7-11, (1986) · Zbl 0621.65058
[191] Torres, P., & Lopez, P. (2000). Overview and possible extensions of shaving techniques for job-shop problems. In 2nd International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (pp. 181-186). Paderborn: Springer. · Zbl 0655.90064
[192] van Beek, P., & Beek, T. (2006). Walsh Backtracking search algorithms. In Rossi, F., & van, P. (Eds.) Handbook of Constraint Programming, chap. 4 (pp. 85-134). Amsterdam: Elsevier. · Zbl 0806.90095
[193] Van Hentenryck, P., Michel, L., & Deville, Y. (1997). Numerica: A Modeling Language for Global Optimization. Cambridge, MA: The MIT Press.
[194] van Iwaarden, R.J. (1996). An improved unconstrained global optimization algorithm. Ph.D. thesis: University of Colorado at Denver.
[195] Vandenbussche, D; Nemhauser, GL, A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Mathematical Programming, 102, 559-575, (2005) · Zbl 1137.90010
[196] Vandenbussche, D; Nemhauser, GL, A polyhedral study of nonconvex quadratic programs with box constraints, Mathematical Programming, 102, 531-557, (2005) · Zbl 1137.90009
[197] Vu, X; Sam-Haroud, D; Faltings, B, Enhancing numerical constraint propagation using multiple inclusion representations, Annals of Mathematics and Artificial Intelligence, 55, 295-354, (2009) · Zbl 1186.68445
[198] Vu, X; Schichl, H; Sam-Haroud, D, Interval propagation and search on directed acyclic graphs for numerical constraint solving, Journal of Global Optimization, 45, 499-531, (2009) · Zbl 1179.90267
[199] Waltz, D. (1975). Understanding line drawings of scenes with shadows. In Winston, P.H. (Ed.) The Pyschology of Computer Vision. New York: McGraw-Hill. · Zbl 0655.90064
[200] Wechsung, A; Schaber, SD; Barton, PI, The cluster problem revisited, Journal of Global Optimization, 58, 429-438, (2014) · Zbl 1297.49046
[201] Zamora, JM; Grossmann, IE, A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms, Journal of Global Optimization, 14, 217-249, (1999) · Zbl 0949.90097
[202] Zorn, K; Sahinidis, NV, Global optimization of general nonconvex problems with intermediate bilinear substructures, Optimization Methods and Software, 29, 442-462, (2013) · Zbl 1285.90043
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.