×

zbMATH — the first resource for mathematics

Global solution of non-convex quadratically constrained quadratic programs. (English) Zbl 1405.90094
Summary: The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of which applies to any QCQP. Let \((P)\) be a QCQP. Our approach to solve \((P)\) is first to build an equivalent mixed-integer quadratic problem \((P^\ast)\). This equivalent problem \((P^\ast)\) has a quadratic convex objective function, linear constraints, and additional variables \(y\) that are meant to satisfy the additional quadratic constraints \(y=xx^{\mathrm{T}}\), where \(x\) are the initial variables of problem \((P)\). We then propose to solve \((P^\ast)\) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
MSC:
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T., Scip: Solving constraint integer programs, Math. Program. Comput., 1, 1, 1-41, (2009) · Zbl 1171.90476
[2] Adjiman, C. S.; Androulakis, I. P.; Floudas, C. A., A global optimization method, αbb, for general twice-differentiable constrained nlps-ii. implementation and computational results, Comput. Chem. Eng., 22, 9, 1159-1179, (1998)
[3] Adjiman, C. S.; Dallwig, S.; Floudas, C. A.; Neumaier, A., A global optimization method, αbb, for general twice-differentiable constrained nlps-i. theoretical advances, Comput. Chem. Eng., 22, 9, 1137-1158, (1998)
[4] Androulakis, I. P.; Maranas, C. D.; Floudas, C. A., abb: A global optimization method for general constrained nonconvex problems, J. Global Optim., 7, 337-363, (1995) · Zbl 0846.90087
[5] Anjos, M. F.; Lasserre, J. B., Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, (2012), Springer: Springer, New York
[6] Anstreicher, K. M., Semidefinite programming versus the reformulation–linearization technique for nonconvex quadratically constrained quadratic programming, J. Global Optim., 43, 2, 471-484, (2009) · Zbl 1169.90425
[7] Audet, C.; Brimberg, J.; Hansen, P.; Le Digabel, S.; Mladenović, N., Pooling problem: Alternate formulations and solution methods, Manage. Sci., 50, 6, 761-776, (2004) · Zbl 1232.90349
[8] Bao, X.; Sahinidis, N. V.; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs, Optim. Methods Softw., 24, 4-5, 485-504, (2009) · Zbl 1179.90252
[9] Bao, X.; Sahinidis, N. V.; Tawarmalani, M., Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Math. Program., 129, 129-157, (2011) · Zbl 1232.49035
[10] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131, (2013) · Zbl 1291.65172
[11] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Waechter, A., Branching and bounds tightening techniques for non-convex minlp, Optim. Methods Softw., 4–5, 24, 597-634, (2009) · Zbl 1179.90237
[12] Billionnet, A., Optimisation discrète, De la modélisation à la résolution par des logiciels de programmation mathématique, (2007), Dunod: Dunod, Paris
[13] Billionnet, A.; Elloumi, S., Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem, Math. Program., 109, 1, 55-68, (2007) · Zbl 1278.90263
[14] Linear reformulations of integer quadratic programs, MCO 2008, September 8–10, 2008, pp. 43–51 · Zbl 1160.90589
[15] Billionnet, A.; Elloumi, S.; Lambert, A., Extending the QCR method to the case of general mixed integer program, Math. Program., 131, 1, 381-401, (2012) · Zbl 1235.90100
[16] Billionnet, A.; Elloumi, S.; Lambert, A., A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation, J. Comb. Optim., 2, 28, 376-399, (2014) · Zbl 1291.90145
[17] Billionnet, A.; Elloumi, S.; Lambert, A., Exact quadratic convex reformulations of mixed-integer quadratically constrained problems, Math. Program., 158, 1, 235-266, (2016) · Zbl 1358.90082
[18] Using a conic bundle method to accelerate both phases of a quadratic convex reformulation, INFORMS J. Comput. 29(2) (2016), pp. 318–331, to appear · Zbl 1371.90098
[19] Billionnet, A.; Elloumi, S.; Plateau, M. C., Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Discrete Appl. Math., 157, 6, 1185-1197, (2009) · Zbl 1169.90405
[20] Solving mixed-integer quadratic programming problems with IBM-CPLEX: A progress report, Proceedings of the Twenty-Sixth RAMP Symposium, Hosei University, Tokyo, 2014, pp. 16–17
[21] Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Waechter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 2, 186-204, (2008) · Zbl 1151.90028
[22] Solving box-constrained nonconvex quadratic programs, Optimization online, 2016
[23] Borchers, B., CSDP, A C Library for semidefinite programming, Optim. Methods Softw., 11, 1, 613-623, (1999) · Zbl 0973.90524
[24] Boukouvala, F.; Misener, R.; Floudas, C. A., Global optimization advances in mixed-integer nonlinear programming, minlp, and constrained derivative-free optimization, cdfo, European J. Oper. Res., 252, 3, 701-727, (2016) · Zbl 1346.90677
[25] Burer, S.; Letchford, A., Non-convex mixed-integer nonlinear programming: A survey, Surv. Oper. Res. Mgmt. Sci., 17, 2, 97-106, (2012)
[26] Burer, S.; Vandenbussche, D., Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 181-195, (2009) · Zbl 1170.90522
[27] Chen, J.; Burer, S., Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 1, 33-52, (2012) · Zbl 1257.90065
[28] Dolan, D.; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (1986) · Zbl 1049.90004
[29] Domes, F.; Neumaier, A., Constraint propagation on quadratic constraints, Constraints, 15, 3, 404-429, (2010) · Zbl 1208.68200
[30] Duran, M. A.; Grossmann, I. E., A mixed-integer nonlinear programming algorithm for process systems synthesis, AIChE J, 32, 4, 592-606, (1986)
[31] Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 307-339, (1986) · Zbl 0619.90052
[32] Falk, J. E.; Soland, R. M., An algorithm for separable nonconvex programming problems, Manage. Sci., 15, 550-560, (1969) · Zbl 0172.43802
[33] Floudas, C. A.; Gounaris, C. E., A review of recent advances in global optimization, J. Global Optim., 45, 1, 3-38, (2009) · Zbl 1180.90245
[34] Floudas, C. A.; Visweswaran, V., A global optimization algorithm (gop) for certain classes of nonconvex nlps-i. theory, Comput. Chem. Eng., 14, 12, 1397-1417, (1990)
[35] Floudas, C. A.; Visweswaran, V., Primal-relaxed dual global optimization approach, J. Optim. Appl., 78, 2, 187-225, (1993) · Zbl 0796.90056
[36] Fortet, R., L’algèbre de Boole et ses applications en Recherche Opérationnelle, Cahiers du Centre d’Etudes de Recherche Opérationnelle, 4, 5-36, (1959) · Zbl 0093.32704
[37] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completness, (1979), W.H. Freeman: W.H. Freeman, San Francisco, CA
[38] Hager, W. W.; Hungerford, J. T., Continuous quadratic programming formulations of optimization problems on graphs, European J. Oper. Res., 240, 2, 328-337, (2015) · Zbl 1357.90166
[39] Hammer, P. L.; Rubin, A. A., Some remarks on quadratic programming with 0-1 variables, Revue Française d’Informatique et de Recherche Opérationnelle, 4, 67-79, (1970) · Zbl 0211.52104
[40] Haverly, C. A., Studies of the behaviour of recursion for the pooling problem, ACM SIGMAP Bull., 26, 19-28, (1978)
[41] Conic Bundle v0.3.102011
[42] IBM-ILOG, IBM ILOG CPLEX 12.6.2 Reference Manual, 2015
[43] Algorithms and software for convex mixed integer nonlinear programs, in Mixed Integer Nonlinear Programming, Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, Jim Luedtke, and Ashutosh Mahajan, eds., Springer New York, 2012, pp. 1–39 · Zbl 1242.90121
[44] IQCP/MIQCP: Library of integer and mixed-integer quadratic quadratically constrained programs, 2013. Available at
[45] Madani, M.; Van Vyve, M., Computationally efficient MIP formulation and algorithms for european day-ahead electricity market auctions, European J. Oper. Res., 242, 2, 580-593, (2015) · Zbl 1341.90092
[46] McCormick, G. P., Computability of global solutions to factorable non-convex programs: Part i - convex underestimating problems, Math. Program., 10, 1, 147-175, (1976) · Zbl 0349.90100
[47] Misener, R.; Floudas, C. A., Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program. B, 136, 1, 155-182, (2012) · Zbl 1257.90079
[48] Misener, R.; Floudas, C. A., GloMIQO: Global mixed-integer quadratic optimizer, J. Global Optim., 57, 1, 3-50, (2013) · Zbl 1272.90034
[49] Misener, R.; Smadbeck, J. B.; Floudas, C. A., Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optim. Methods Softw., 30, 1, 215-249, (2015) · Zbl 1325.90071
[50] Moré, J. J.; Toraldo, G., Algorithms for bound constrained quadratic programming problems, Numer. Math., 55, 4, 377-400, (1989) · Zbl 0675.65061
[51] Baron 9.0.4: Global Optimization of Mixed-Integer Nonlinear Programs. User’s Manual2010
[52] Saxena, A.; Bonami, P.; Lee, J., Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations, Math. Program., 130, 359-413, (2011) · Zbl 1229.90144
[53] Sherali, H. D.; Adams, W. P., A hierarchy of relaxation between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 411-430, (1990) · Zbl 0712.90050
[54] Tawarmalani, M.; Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Math. Program., 99, 3, 563-591, (2004) · Zbl 1062.90041
[55] Tawarmalani, M.; Sahinidis, N. V., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, (2002), Kluwer Academic Publishing: Kluwer Academic Publishing, Dordrecht, The Netherlands · Zbl 1031.90022
[56] Tawarmalani, M.; Sahinidis, N. V., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249, (2005) · Zbl 1099.90047
[57] Vandenbussche, D.; Nemhauser, G., A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Math. Program., 102, 3, 259-275, (2005)
[58] Scip: Global optimization of mixed-integer nonlinear programs in a branch-and-cut frameworkOptim. Methods Softw2016131
[59] Visweswaran, V.; Floudast, C. A., A global optimization algorithm (gop) for certain classes of nonconvex nlps-ii. application of theory and test problems, Comput. Chem. Eng., 14, 12, 1419-1434, (1990)
[60] Visweswaran, V.; Floudast, C. A., New properties and computational improvement of the gop algorithm for problems with quadratic objective functions and constraints, J. Global Optim., 3, 4, 439-462, (1993) · Zbl 0795.90070
[61] Zorn, K.; Sahinidis, N. V., Computational experience with applications of bilinear cutting planes, Ind. Eng. Chem. Res., 52, 22, 7514-7525, (2013)
[62] Zorn, K.; Sahinidis, N. V., Global optimization of general non-convex problems with intermediate bilinear substructures, Optim. Methods Softw., 29, 3, 442-462, (2014) · 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.