Abstract
This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. These methods can be viewed as generalizations of techiniques for mixed-integer linear programming. We also present brief computational results to indicate the strength and computational requirements of these methods.
Author supported in part by NSF Grant CCF-0545514.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
K. Abhishek, S. Leyffer, and J.T. Linderoth, FilMINT: An outer-approximation-based solver for convex mixed-integer nonlinear programs, IN- FORMS Journal on Computing, 22 (2010), pp. 555–567.
T.K. Achterberg, T. Berthold and K.T. Wolter, Constraint integer programming: A new approach to integrate cp and mip, Lecture Notes in Computer Science, 5015 (2008), pp. 6–20.
F.A. Al-Khayyal, Generalized bilinear programming, Part i: Models, applications, and linear programming relaxations, European Journal of Operational Research, 60 (1992), pp. 306–314.
F.A. Al-Khayyal and J.E. Falk, Jointly constrained biconvex programming, Math. Oper. Res., 8 (1983), pp. 273–286.
F. Alizadeh and D. Goldfarb, Second-order cone programming, Math. Program., 95 (2003), pp. 3–51. ISMP 2000, Part 3 (Atlanta, GA).
K.M. Anstreicher and S. Burer, Computable representations for convex hulls of low-dimensional quadratic forms, with K. Anstreicher, Mathematical Programming (Series B), 124(1–2), pp. 33–43 (2010).
A. Atamt¨urk and V. Narayanan, Conic mixed-integer rounding cuts, Math. Program., 122 (2010), pp. 1–20.
E. Balas, Disjunctive programming: properties of the convex hull of feasible points, Discrete Appl. Math., 89 (1998), pp. 3–44.
E. Balas, S. Ceria, and G. Cornu´ejols, A lift-and-project cutting plane algorithm for mixed 0–1 programs, Mathematical Programming, 58 (1993), pp. 295–324.
A. Beck, Quadratic matrix programming, SIAM J. Optim., 17 (2006), pp. 1224–1238 (electronic).
P. Belotti, Disjunctive cuts for non-convex MINLP, IMA Volume Series, Springer 2010, accepted. http://myweb.clemson.edu/∼pbelott/papers/belotti-disj-MINLP.pdf.
A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second-order cone, Math. Oper. Res., 26 (2001), pp. 193–205.
A. Berman and N. Shaked-Monderer, Completely Positive Matrices, World Scientific, 2003.
D. Bienstock and M. Zuckerberg, Subset algebra lift operators for 0–1 integer programming, SIAM J. Optim., 15 (2004), pp. 63–95 (electronic).
I. Bomze and F. Jarre, A note on Burer’s copositive representation of mixed-binary QPs, Optimization Letters, 4 (2010), pp. 465–472.
P. Bonami, L. Biegler, A. Conn, G. Cornu´ejols, I. Grossmann, C. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya, and A. W¨achter, An algorithmic framework for convex mixed-integer nonlinear programs., Discrete Optimiza- tion, 5 (2008), pp. 186–204.
S. Burer, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Mathematical Programming Computation, 2(1), pp 1–19 (2010).
, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), pp. 479–495.
S. Burer and A.N. Letchford, On nonconvex quadratic programming with box constraints, SIAM J. Optim., 20 (2009), pp. 1073–1089.
S. Burer and D. Vandenbussche, Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43 (2009), pp. 181–195.
D. Coppersmith, O. G¨unl¨uk, J. Lee, and J. Leung, A polytope for a product of a real linear functions in 0/1 variables, manuscript, IBM, Yorktown Heights, NY, December 2003.
G. Cornu´ejols, Combinatorial optimization: packing and covering, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.
R.W. Cottle, G.J. Habetler, and C.E. Lemke, Quadratic forms semi-definite over convex cones, in Proceedings of the Princeton Symposium on Mathematical Programming (Princeton Univ., 1967), Princeton, N.J., 1970, Princeton Univ. Press, pp. 551–565.
G. Danninger and I.M. Bomze, Using copositivity for global optimality criteria in concave quadratic programming problems, Math. Programming, 62 (1993), pp. 575–580.
G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large-scale traveling-salesman problem, J. Operations Res. Soc. Amer., 2 (1954), pp. 393–410.
E. de Klerk and D.V. Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12 (2002), pp. 875–892.
See the website: www.gamsworld.org/global/globallib/globalstat.htm.
R. Horst and N.V. Thoai, DC programming: overview, J. Optim. Theory Appl., 103 (1999), pp. 1–43.
M. Jach, D. Michaels, and R. Weismantel, The convex envelope of (N − 1)-convex fucntions, SIAM J. Optim., 19 (2008), pp. 1451–1466.
R. Jeroslow, There cannot be any algorithm for integer programming with quadratic constraints., Operations Research, 21 (1973), pp. 221–224.
S. Kim and M. Kojima, Second order cone programming relaxation of non-convex quadratic optimization problems, Optim. Methods Softw., 15 (2001), pp. 201–224.
, Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26 (2003), pp. 143–154.
M. Kojima and L. Tunc¸el, Cones of matrices and successive convex relaxations of nonconvex sets, SIAM J. Optim., 10 (2000), pp. 750–778.
J.B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817.
M. Laurent, A comparison of the Sherali-Adams, Lov´asz-Schrijver, and Lasserre relaxations for 0–1 programming, Math. Oper. Res., 28 (2003), pp. 470–496.
J. Linderoth, A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program., 103 (2005), pp. 251–282.
L. Lov´asz and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM Journal on Optimization, 1 (1991), pp. 166–190.
T. Matsui, NP-hardness of linear multiplicative programming and related problems, J. Global Optim., 9 (1996), pp. 113–119.
J.E. Maxfield and H. Minc, On the matrix equation X′X = A, Proc. Edinburgh Math. Soc. (2), 13 (1962/1963), pp. 125–129.
G.P. McCormick, Computability of global solutions to factorable nonconvex programs. I. Convex underestimating problems, Math. Programming, 10 (1976), pp. 147–175.
See the website: http://www.gamsworld.org/minlp/.
K.G. Murty and S.N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Programming, 39 (1987), pp. 117–129.
G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience, 1999.
M. Padberg, The Boolean quadric polytope: some characteristics, facets and relatives, Math. Programming, 45 (1989), pp. 139–172.
P. Pardalos, Global optimization algorithms for linearly constrained indefinite quadratic problems, Computers and Mathematics with Applications, 21 (1991), pp. 87–97.
P.M. Pardalos and S.A. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard, J. Global Optim., 1 (1991), pp. 15–22.
P. Parrilo, Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization, PhD thesis, California Institute of Technology, 2000.
G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Mathematics of Operations Research, 23 (1998), pp. 339–358.
J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim., 18 (2007), pp. 223–241.
, Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optim., 6 (2009), pp. 231–241.
N.V. Sahinidis, BARON: a general purpose global optimization software package, J. Glob. Optim., 8 (1996), pp. 201–205.
A. Saxena, P. Bonami, and J. Lee, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Mathematical Programming (Series B), 124(1–2), pp. 383–411 (2010). http://dx.doi.org/10.1007/s10107-010-0371-9.
, Convex relaxations of non-convex mixed integer quadratically constrained programs: Projected formulations, 2010. To appear in Mathematical Programming. http://dx.doi.org/10.1007/s10107-010-0340-3.
H.D. Sherali andW.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.
H.D. Sherali andW.P. Adams, A Reformulation–linearization Technique (RLT) for Solving Discrete and Continuous Nonconvex Problems, Kluwer, 1997.
N. Shor, Quadratic optimization problems, Soviet Journal of Computer and Systems Science, 25 (1987), pp. 1–11. Originally published in Tekhnicheskaya Kibernetika, 1:128–139, 1987.
J.F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Math. Oper. Res., 28 (2003), pp. 246–267.
M. Tawarmalani and N.V. Sahinidis, Convexification and global optimization in continuous and mixed-integer nonlinear programming, Vol. 65 of Nonconvex Optimization and its Applications, Kluwer Academic Publishers, Dordrecht, 2002. Theory, algorithms, software, and applications.
J.P. Vielma, S. Ahmed, and G.L. Nemhauser, A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs, INFORMS J. Comput., 20 (2008), pp. 438–450.
Y. Yajima and T. Fujie, A polyhedral approach for nonconvex quadratic programming problems with box constraints, J. Global Optim., 13 (1998), pp. 151–170.
Y. Ye and S. Zhang, New results on quadratic minimization, SIAM J. Optim., 14 (2003), pp. 245–267 (electronic).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer Science+Business Media, LLC
About this paper
Cite this paper
Burer, S., Saxena, A. (2012). The MILP Road to MIQCP. In: Lee, J., Leyffer, S. (eds) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol 154. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1927-3_13
Download citation
DOI: https://doi.org/10.1007/978-1-4614-1927-3_13
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-1926-6
Online ISBN: 978-1-4614-1927-3
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)