Abstract
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities by using the equation Y = x x T. We use the concave constraint \( 0 \succcurlyeq Y - x x^T \) to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix Y − x x T with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the width of the disjunction. We also use the convex SDP constraint \( Y - x x^T \succcurlyeq 0\) to derive convex quadratic cuts and combine both approaches in a cutting plane algorithm. We present preliminary computational results to illustrate our findings.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anstreicher, K.M.: Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming. Preprint. Optimization Online (May 2007)
Balas, E.: Disjunctive programming: properties of the convex hull of feasible points. Disc. Appl. Math. 89(1-3), 3–44 (1998)
Balas, E., Ceria, S., Cornuéjols, G.: A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program. 58, 295–324 (1993)
Balas, E., Saxena, A.: Optimizing over the split closure. MSRR# 674, Tepper School of Business, Carnegie Mellon Univ., Math. Program. A (to appear, 2005)
Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N., Wächter, A.: An Algorithmic Framework for Convex Mixed-integer Nonlinear Programs. Discrete Optimization (in press)
Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Programming (to appear)
Cornuéjols, G.: Revival of the Gomory cuts in the 1990’s. Annals of Operations Research 149(1), 63–66 (2007)
Fischetti, M., Lodi, A.: Optimizing over the first Chvatal closure. Mathematical Programming (to appear)
Fletcher, R., Leyffer, S.: User Manual for FilterSQP. Numerical Analysis Report NA/181, Dundee University (1998)
Jeroslow, R.G.: There cannot be any algorithm for integer programming with quadratic constraints. Operations Research 21(1), 221–224 (1973)
GLOBALLib, http://www.gamsworld.org/global/globallib/globalstat.htm
Lee, S., Grossmann, I.E.: A global optimization algorithm for nonconvex generalized disjunctive programming and applications to process systems. Computers and Chemical Engineering 25, 1675–1697 (2001)
Kim, S., Kojima, M.: Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods and Software 15, 201–204 (2001)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part I Convex underestimating problems. Math. Prog. 10, 147–175 (1976)
Nowak, I., Alperin, H., Vigerske, S.: LaGO - An object oriented library for solving MINLPs. In: Bliek, C., et al. (eds.) Global Optimization and Constraint Satisfaction, pp. 32–42. Springer, Berlin (2003)
Nowak, I.: Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming. Birkhauser, Basel (2005)
Vigerske, S.: http://projects.coin-or.org/LaGO
Saxena, A., Goyal, V., Lejeune, M.: MIP Reformulations of the Probabilistic Set Covering Problem (2007) Optmization Online (e-print), http://www.optimization-online.org/DB_HTML//02/1579.html
Sen, S.: Relaxations for probabilistically constrained programs with discrete random variables. Operations Research Letters 11(2), 81–86 (1992)
Sherali, H.D., Adams, W.P.: A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer, Dordecht (1998)
Sherali, H.D., Fraticelli, B.M.P.: Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22, 233–261 (2002)
Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods and Software 11-12, 625–653 (1999)
Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Boston (2002)
Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed integer nonlinear programs: A theoretical and computational study. Math. Prog. 99(3), 563–591 (2004)
Vandenbussche, D., Nemhauser, G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Prog. 102(3), 531–556 (2005)
Vandenbussche, D., Nemhauser, G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Prog. 102(3), 559–575 (2005)
Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Prog. 106(1), 25–57 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Saxena, A., Bonami, P., Lee, J. (2008). Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2008. Lecture Notes in Computer Science, vol 5035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68891-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-68891-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68886-0
Online ISBN: 978-3-540-68891-4
eBook Packages: Computer ScienceComputer Science (R0)