Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. (English) Zbl 1400.90239
Summary: We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal-Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex
quadratic programs with linear constraints.
MSC:
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | An, LTH; Tao, PD, A branch and bound method via d.c. optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems, J. Glob. Optim., 13, 171-206, (1998) · Zbl 0912.90233 · doi:10.1023/A:1008240227198 |
| [2] | Andersen, M., Dahl, J., Vandenberghe, L.: CVXOPT user’s guide, release 1.1.8 (2015) |
| [3] | Anstreicher, K, On convex relaxations for quadratically constrained quadratic programming, Math. Program., 136, 233-251, (2012) · Zbl 1267.90103 · doi:10.1007/s10107-012-0602-3 |
| [4] | Anstreicher, K; Burer, S, Computable representations for convex hulls of low-dimensional quadratic forms, Math. Program., 124, 33-43, (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9 |
| [5] | Anstreicher, KM, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, J. Glob. Optim., 43, 471-484, (2008) · Zbl 1169.90425 |
| [6] | Barahona, F, On cuts and matchings in planar graphs, Math. Program., 60, 53,58, (1993) · Zbl 0795.90017 · doi:10.1007/BF01580600 |
| [7] | Barahona, F; Grötschel, M; Jünger, M; Reinelt, G, Experiments in quadratic 01 programming, Math. Program., 44, 127-137, (1989) · Zbl 0677.90046 · doi:10.1007/BF01587084 |
| [8] | Barahona, F; Mahjoub, A, On the cut polytope, Math. Program., 36, 157-173, (1986) · Zbl 0616.90058 · doi:10.1007/BF02592023 |
| [9] | Bliek, C., Bonami, P., Lodi, A.: Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report. In: Proceedings of the Twenty-Sixth RAMP Symposium, pp. 171-180 (2014) |
| [10] | Boros, E; Crama, Y; Hammer, PL, Chvátal cuts and odd cycle inequalities in quadratic 0-1 optimization, SIAM J. Discrete Math., 5, 163-177, (1992) · Zbl 0761.90069 · doi:10.1137/0405014 |
| [11] | Boros, E; Hammer, PL, Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions, Math. Oper. Res., 18, 245-253, (1993) · Zbl 0778.90041 · doi:10.1287/moor.18.1.245 |
| [12] | Burer, S; Monteiro, DR, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 329-357, (2003) · Zbl 1030.90077 · doi:10.1007/s10107-002-0352-8 |
| [13] | Burer, S, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math. Program. Comput., 2, 119, (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8 |
| [14] | Burer, S; Chen, J, Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 33-52, (2012) · Zbl 1257.90065 · doi:10.1007/s12532-011-0033-9 |
| [15] | Burer, S; Letchford, A, On nonconvex quadratic programming with box constriants, SIAM J. Optim., 20, 1073-1089, (2009) · Zbl 1201.90146 · doi:10.1137/080729529 |
| [16] | Burer, S., Monteiro, R., Choi, C.: SDPLR 1.03-beta user’s guide (short version) (2009). http://sburer.github.io/files/SDPLR-1.03-beta-usrguide.pdf |
| [17] | Burer, S; Vandenbussche, D, Globally solving box-constrained nonconvex quadratic programs with semdefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 181-195, (2009) · Zbl 1170.90522 · doi:10.1007/s10589-007-9137-6 |
| [18] | Caprara, A; Fischetti, M, \({\{0, \frac{1}{2}\}}\) chvátal-Gomory cuts, Math. Program., 74, 221-235, (1996) · Zbl 0855.90088 |
| [19] | Chvátal, V, Edmonds polytopes and weakly Hamiltonian graphs, Math. Program., 5, 29-40, (1973) · Zbl 0267.05118 · doi:10.1007/BF01580109 |
| [20] | Dolan, E; Moré, J, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [21] | Dong, H, Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations, SIAM J Optim, 26, 1962-1985, (2014) · Zbl 1348.90473 · doi:10.1137/140960657 |
| [22] | Dong, H., Linderoth, J.: On valid inequalities for quadratic programming with continuous variables and binary indicators. In: IPCO 2013: The Sixteenth Conference on Integer Programming and Combinatorial Optimization, vol. 7801, pp. 169-180. Springer (2013) · Zbl 1372.90073 |
| [23] | Gomory, RE, Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Mon., 64, 275-278, (1958) · Zbl 0085.35807 · doi:10.1090/S0002-9904-1958-10224-4 |
| [24] | Hansen, P; Jaumard, B; Ruiz, M; Xiong, J, Global minimization of indefinite quadratic functions subject to box constraints, Naval Res. Logist., 40, 373-392, (1993) · Zbl 0782.90071 · doi:10.1002/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A |
| [25] | Horst, H., Pardalos, P.M., Thoai, V.: Introduction to Global Optimization, 2nd edn. Kluwer, Dordrecht (2000) · Zbl 0966.90073 · doi:10.1007/978-1-4615-0015-5 |
| [26] | Koster, A; Zymolka, A; Kutschka, M, Algorithms to separate 0,1/2-chvátal-Gomory cuts, Algorithmica, 55, 375-391, (2009) · Zbl 1189.90132 · doi:10.1007/s00453-008-9218-7 |
| [27] | McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665 |
| [28] | Misener, R; Smadbeck, JB; Floudas, CA, Dynamically-generated cutting planes for mixed-integer quadratically-constrained quadratic programs and their incorporation into glomiqo 2.0, Optim. Methods Softw., 30, 215-249, (2015) · Zbl 1325.90071 · doi:10.1080/10556788.2014.916287 |
| [29] | Padberg, M, The Boolean quadric polytope: some characterics, facets, and relatives, Math. Program., 45, 139-172, (1989) · Zbl 0675.90056 · doi:10.1007/BF01589101 |
| [30] | Padberg, MW, Total unimodularity and the Euler-subgraph problem, Oper. Res. Lett., 7, 173-179, (1988) · Zbl 0652.90075 · doi:10.1016/0167-6377(88)90024-7 |
| [31] | Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Math. Program. 130, 359-413 (2011). Version with appendix available at http://www.optimization-online.org/DB_FILE/2008/11/2145.pdf · Zbl 1229.90144 |
| [32] | Sherali, H; Tuncbilek, C, A new reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Glob. Optim., 7, 1-31, (1995) · Zbl 0844.90064 · doi:10.1007/BF01100203 |
| [33] | Sherali HD, Alameddine AR (1990) An explicit characterization of the convex envelope of a bivariate function over special polytopes. Ann. Oper. Res. Comput. Methods Glob. Optim. 25(1): 197-210 · Zbl 0723.90073 |
| [34] | Shor, NZ, Quadratic optimization problems, Sov. J. Circuits Syst. Sci., 25, 1-11, (1987) · Zbl 0655.90055 |
| [35] | Simone, CD, The cut polytope and the Boolean quadric polytope, Discrete Math., 79, 71-75, (1989) · Zbl 0683.90068 · doi:10.1016/0012-365X(90)90056-N |
| [36] | Sturm, JF, Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12, 625-653, (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [37] | The MOSEK command line tool. Version 7.1 (revision 51) (2016). http://docs.mosek.com/7.1/tools/index.html |
| [38] | Tawarmalani, M; Sahinidis, N, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8 |
| [39] | 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 · doi:10.1007/s10107-003-0467-6 |
| [40] | Vandenbussche, D; Nemhauser, GL, A branch-and-cut algorithm for nonconvex quadratic programs with box constraints, Math. Program., 102, 559-575, (2005) · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7 |
| [41] | Yajima, Y; Fujie, T, A polyhedral approach for nonconvex quadratic programming problems with box constraints, J. Glob. Optim., 13, 151-170, (1998) · Zbl 0912.90234 · doi:10.1023/A:1008293029350 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
