Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
Tóm tắt
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.
Tài liệu tham khảo
An, L.T.H., Tao, P.D.: 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)
Andersen, M., Dahl, J., Vandenberghe, L.: CVXOPT user’s guide, release 1.1.8 (2015)
Anstreicher, K.: On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136, 233–251 (2012)
Anstreicher, K., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010)
Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43(2), 471–484 (2008)
Barahona, F.: On cuts and matchings in planar graphs. Math. Program. 60, 53,58 (1993)
Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: Experiments in quadratic 01 programming. Math. Program. 44, 127–137 (1989)
Barahona, F., Mahjoub, A.: On the cut polytope. Math. Program. 36, 157–173 (1986)
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)
Boros, E., Crama, Y., Hammer, P.L.: Chvátal cuts and odd cycle inequalities in quadratic 0–1 optimization. SIAM J. Discrete Math. 5(2), 163–177 (1992)
Boros, E., Hammer, P.L.: Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions. Math. Oper. Res. 18(1), 245–253 (1993)
Burer, S., Monteiro, D.R.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329–357 (2003). https://doi.org/10.1007/s10107-002-0352-8
Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2(1), 119 (2010)
Burer, S., Chen, J.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33–52 (2012)
Burer, S., Letchford, A.: On nonconvex quadratic programming with box constriants. SIAM J. Optim. 20(2), 1073–1089 (2009)
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
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)
Caprara, A., Fischetti, M.: \({\{0, \frac{1}{2}\}}\) chvátal-gomory cuts. Math. Program. 74, 221–235 (1996)
Chvátal, V.: Edmonds polytopes and weakly Hamiltonian graphs. Math. Program. 5, 29–40 (1973)
Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Dong, H.: Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM J Optim 26(3), 1962–1985 (2014). https://doi.org/10.1137/140960657
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)
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Mon. 64, 275–278 (1958)
Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Naval Res. Logist. 40(3), 373–392 (1993)
Horst, H., Pardalos, P.M., Thoai, V.: Introduction to Global Optimization, 2nd edn. Kluwer, Dordrecht (2000)
Koster, A., Zymolka, A., Kutschka, M.: Algorithms to separate 0,1/2-Chvátal–Gomory cuts. Algorithmica 55(2), 375–391 (2009)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10, 147–175 (1976)
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.0. Optim. Methods Softw. 30, 215–249 (2015)
Padberg, M.: The boolean quadric polytope: some characterics, facets, and relatives. Math. Program. 45, 139–172 (1989)
Padberg, M.W.: Total unimodularity and the Euler-subgraph problem. Oper. Res. Lett. 7(4), 173–179 (1988)
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
Sherali, H., Tuncbilek, C.: A new reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7, 1–31 (1995)
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
Shor, N.Z.: Quadratic optimization problems. Sov. J. Circuits Syst. Sci. 25(6), 1–11 (1987)
Simone, C.D.: The cut polytope and the boolean quadric polytope. Discrete Math. 79, 71–75 (1989)
Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999)
The MOSEK command line tool. Version 7.1 (revision 51) (2016). http://docs.mosek.com/7.1/tools/index.html
Tawarmalani, M., Sahinidis, N.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005)
Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004)
Vandenbussche, D., Nemhauser, G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102, 559–575 (2005)
Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151–170 (1998)