×

zbMATH — the first resource for mathematics

Solving quadratic programming by cutting planes. (English) Zbl 1411.90247

MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] T. Achterberg, D. Junglas, and R. Wunderling, Deterministic Parallelization through Atomic Task Computation, US Patent, December 3, 2013; available at .
[2] K. Anstreicher, On convex relaxations for quadratically constrained quadratic programming, Math. Program., 136 (2012), pp. 233–251. · Zbl 1267.90103
[3] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, Mixed-integer nonlinear optimization, Acta Numer., 22 (2013), pp. 1–131.
[4] I. Bomze, M. Dür, E. de Klerk, C. Roos, A. Quist, and T. Terlaky, On copositive programming and standard quadratic optimization problems, J. Global Optim., 18 (2000), pp. 301–320. · Zbl 0970.90057
[5] I. M. Bomze, On standard quadratic optimization problems, J. Global Optim., 13 (1998), pp. 369–387.
[6] I. M. Bomze, M. Locatelli, and F. Tardella, New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability, Math. Program., 115 (2008), pp. 31–64. · Zbl 1171.90007
[7] 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., 10 (2018), pp. 333–382. · Zbl 1400.90239
[8] C. Brás, G. Eichfelder, and J. Júdice, Copositivity tests based on the linear complementarity problem, Comput. Optim. Appl., 63 (2016), pp. 461–493.
[9] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120 (2009), pp. 479–495. · Zbl 1180.90234
[10] S. Burer, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Program. Comput., 2 (2010), pp. 1–19. · Zbl 1190.90135
[11] S. Burer and D. Vandenbussche, Globally solving box-constrained nonconvex quadratic programs with semdefinite-based finite branch-and-bound, Comput. Optim. Appl., 43 (2009), pp. 181–195. · Zbl 1170.90522
[12] A. Caprara, M. Carvalho, A. Lodi, and G. J. Woeginger, Bilevel knapsack with interdiction constraints, INFORMS J. Comput., 28 (2016), pp. 319–333. · Zbl 1343.90075
[13] A. Caprara, D. Pisinger, and P. Toth, Exact solution of the quadratic knapsack problem, INFORMS J. Comput., 11 (1999), pp. 125–137. · Zbl 1034.90521
[14] J. Chen and S. Burer, Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4 (2012), pp. 33–52. · Zbl 1257.90065
[15] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201–213. · Zbl 1049.90004
[16] M. Dür, Copositive programming: A survey, in Recent Advances in Optimization and Its Applications in Engineering: The 14th Belgian-French-German Conference on Optimization, Springer, Berlin, 2010, pp. 3–20.
[17] G. Gallo, P. Hammer, and B. Simeone, Quadratic knapsack problems, in Combinatorial Optimization, M. Padberg, ed., Math. Program. Stud. 12, Springer, Berlin, 1980, pp. 132–149. · Zbl 0462.90068
[18] L. Gibbons, D. Hearn, P. Pardalos, and M. Ramana, Continuous characterizations of the maximum clique problem, Math. Oper. Res., 22 (1997), pp. 754–768. · Zbl 0883.90098
[19] IBM, Boolean quadric polytope (BQP) cuts, in CPLEX 12.6.3 User’s Manual, , (March 18, 2016).
[20] IBM, Deterministic time limit, in CPLEX 12.6.3 User’s Manual, , (March 18, 2016).
[21] IBM CPLEX Optimizer, .
[22] R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, eds., The IBM Research Symposia Series, Springer, New York, 1972, pp. 85–103.
[23] A. Lodi, T. K. Ralphs, and G. J. Woeginger, Bilevel programming and the separation problem, Math. Program., 146 (2014), pp. 437–458. · Zbl 1401.90128
[24] G. McCormick, Computability of global solutions to factorable nonconvex programs: Part \textupI – convex underestimating problems, Math. Program., 10 (1976), pp. 147–175. · Zbl 0349.90100
[25] R. Misener and C. A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer, J. Global Optim., 57 (2013), pp. 3–50. · Zbl 1272.90034
[26] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17 (1965), pp. 533–540.
[27] J. Schweiger, Nonlinearity and uncertainty in energy networks, Ph.D. thesis, Technische Universität Berlin, 2017.
[28] A. Scozzari and F. Tardella, A clique algorithm for standard quadratic programming, Discrete Appl. Math., 156 (2008), pp. 2439–2448. · Zbl 1163.90691
[29] H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), pp. 411–430. · Zbl 0712.90050
[30] H. D. Sherali and A. Alameddine, A new reformulation-linearization technique for bilinear programming problems, J. Global Optim., 2 (1992), pp. 379–410. · Zbl 0791.90056
[31] M. Tawarmalani and N. V. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Kluwer Academic, Boston, MA, 2002. · Zbl 1031.90022
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.