×

zbMATH — the first resource for mathematics

Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs. (English) Zbl 1458.90486
MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
Software:
BARON; GloMIQO; LAPACK
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] T. Achterberg, T. Koch, and A. Martin, Branching rules revisited, Oper. Res. Lett., 33 (2005), pp. 42-54. · Zbl 1076.90037
[2] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, Software Environ. Tools 9, SIAM, Philadelphia, 1999, https://doi.org/10.1137/1.9780898719604. · Zbl 0934.65030
[3] I. P. Androulakis, C. D. Maranas, and C. A. Floudas, \( \alpha\) BB: A global optimization method for general constrained nonconvex problems, J. Global Optim., 7 (1995), pp. 337-363. · Zbl 0846.90087
[4] D. Applegate, R. Bixby, V. Chvátal, and W. Cook, A Recipe for Semidefinite Relaxations of (0,1) Quadratic Programming, Tech. report, DIMACS, Piscataway, NJ, 1995.
[5] X. Bao, A. Khajavirad, N. V. Sahinidis, and M. Tawarmalani, Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7 (2015), pp. 1-37. · Zbl 1317.90243
[6] X. Bao, N. V. Sahinidis, and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Math. Program., 129 (2011), pp. 129-157. · Zbl 1232.49035
[7] A. Billionnet, S. Elloumi, and A. Lambert, An efficient compact quadratic convex reformulation for general integer quadratic programs, Comput. Optim. Appl., 54 (2013), pp. 141-162. · Zbl 1267.90092
[8] A. Billionnet, S. Elloumi, and M. C. Plateau, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Discrete Appl. Math., 157 (2009), pp. 1185-1197. · Zbl 1169.90405
[9] I. M. Bomze and M. Locatelli, Undominated D.C. decompositions of quadratic functions and applications to branch-and-bound approaches, Comput. Optim. Appl., 28 (2004), pp. 227-245. · Zbl 1056.90112
[10] P. Bonami, O. Günlük, and J. Linderoth, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Math. Program. Comput., (2018), pp. 1-50. · Zbl 1400.90239
[11] C. Buchheim and A. Wiegele, Semidefinite relaxations for non-convex quadratic mixed-integer programming, Math. Program., 141 (2013), pp. 435-452. · Zbl 1280.90091
[12] C. J. Nohra, A. U. Raghunathan, and N. V. Sahinidis, A Test Set of Quadratic, Binary Quadratic and Integer Quadratic Programs, available at ftp://ftp.merl.com/pub/raghunathan/MIQP-TestSet/.
[13] A. Faye and F. Roupin, Partial Lagrangian relaxation for general quadratic programming, 4OR, 5 (2007), pp. 75-88. · Zbl 1142.90025
[14] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), pp. 1115-1145. · Zbl 0885.68088
[15] G. Golub and C. F. V. Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[16] P. L. Hammer and A. A. Rubin, Some remarks on quadratic programming with \(0-1\) variables, Rev. Française Informat. Recherche Opérationnielle, 4 (1970), pp. 67-79. · Zbl 0211.52104
[17] A. Khajavirad and N. V. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput., 10 (2018), pp. 383-421. · Zbl 1400.90227
[18] E. M. Loiola, N. M. M. de Abreu, P. Boaventura-Netto, P. Hahn, and T. Querido, A survey for the quadratic assignment problem, European J. Oper. Res., 176 (2007), pp. 657-690. · Zbl 1103.90058
[19] M. K\il\inç and N. V. Sahinidis, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON, Optim. Methods Softw., 33 (2018), pp. 540-562. · Zbl 1398.90110
[20] G. P. McCormick, Computability of global solutions to factorable nonconvex programs. I. Convex underestimating problems, Math. Program., 10 (1976), pp. 147-175. · Zbl 0349.90100
[21] R. Misener, J. B. Smadbeck, and C. A. Floudas, Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods Softw., 30 (2015), pp. 215-249. · Zbl 1325.90071
[22] P. M. Pardalos, J. H. Glick, and J. B. Rosen, Global minimization of indefinite quadratic problems, Computing, 539 (1987), pp. 281-291. · Zbl 0627.65072
[23] A. Phillips and J. Rosen, A quadratic assignment formulation of the molecular conformation problem, J. Global Optim., 4 (1994), pp. 229-241. · Zbl 0797.90116
[24] N. V. Sahinidis, BARON: A general purpose global optimization software package, J. Global Optim., 8 (1996), pp. 201-205. · Zbl 0856.90104
[25] H. D. Sherali and W. P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optim. Appl. 31, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1999. · Zbl 0926.90078
[26] N. Shor, Quadratic optimization problems, Soviet J. Comput. Systems Sci., 25 (1987), pp. 1-11. · Zbl 0655.90055
[27] M. Tawarmalani and N. V. Sahinidis, Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Math. Program., 99 (2004), pp. 563-591. · Zbl 1062.90041
[28] H. Tuy, D.C. optimization: Theory, methods and algorithms, in Handbook of Global Optimization, Springer-Verlag, Boston, MA, 1995, pp. 149-216. · Zbl 0832.90111
[29] K. Zorn and N. V. Sahinidis, Global optimization of general nonconvex problems with intermediate bilinear substructures, Optim. Methods Softw., 29 (2013), pp. 442-462. · 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.