Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Unbounded convex sets for non-convex mixed-integer quadratic programming

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a face of a set in the family. Some fundamental properties of the convex sets are derived, along with connections to some other well-studied convex sets. Several classes of valid and facet-inducing inequalities are also derived.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Anstreicher, K.M., Burer, S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arkinstall, J.R.: Minimal requirements for Minkowski’s theorem in the plane. Bull. Aust. Math. Soc. 22, 259–283 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  3. Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003)

    Book  MATH  Google Scholar 

  4. Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and Software for Convex Mixed Integer Nonlinear Programs. Technical Report #1664, Computer Sciences Department, University of Wisconsin–Madison (2009)

  5. Boros, E., Hammer, P.L.: Cut-polytopes, Boolean quadric polytopes and nonnegative quadratic pseudo-Boolean functions. Math. Oper. Res. 18, 245–253 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  6. Burer, S., Letchford, A.N.: On non-convex quadratic programming with box constraints. SIAM J. Optim. 20, 1073–1089 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Cook, W., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  8. Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)

    MATH  Google Scholar 

  9. Dickinson, P.J.C., Gijben, L.: On the Computational Complexity of Membership Problems for the Completely Positive Cone and its Dual. Technical Report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen (2011)

  10. Dür, M.: Copositive programming: a survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering. Springer, Berlin (2010)

    Google Scholar 

  11. Fujie, T., Kojima, M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Glob. Optim. 10, 367–380 (1997)

    Google Scholar 

  12. Galli, L., Kaparis, K., Letchford, A.N.: Gap inequalities for non-convex mixed-integer quadratic programs. Oper. Res. Lett. (2011, to appear)

  13. Gosset, T.: On the regular and semi-regular figures in space of \(n\) dimensions. Messenger Math. 29, 43–48 (1990)

    Google Scholar 

  14. Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive techniques. Optim. Eng. 3, 227–252 (2002)

    Google Scholar 

  15. Helmberg, C., Rendl, F., Weismantel, R.: A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4, 197–215 (2002)

    Article  MathSciNet  Google Scholar 

  16. Hill, R.D., Waters, S.R.: On the cone of positive semidefinite matrices. Linear Algebra Appl. 90, 81–88 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  17. Hiriart-Urruty, J.B., Lémaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin (2004)

    Google Scholar 

  18. Jünger, M., Kaibel, V.: Box-inequalities for quadratic assignment polytopes. Math. Program. 91, 175–197 (2001)

    Google Scholar 

  19. Khachiyan, L., Porkolab, L.: Integer optimization on convex semialgebraic sets. Discret. Comput. Geom. 23, 207–224 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  20. Letchford, A.N.: Integer quadratic quasi-polyhedra. In: Eisenbrand F., Shepherd B. (eds.) Integer Programming and Combinatorial Optimization XIV. Lecture Notes in Computer Science, vol. 6080, Springer, Berlin (2010)

  21. Lémaréchal, C., Oustry, F.: SDP relaxations in combinatorial optimization from a Lagrangian viewpoint. In: Hadjisawas, N., Pardalos, P.M. (eds.) Advances in Convex Analysis and Global Optimization. Kluwer, Dortrecht (2001)

    Google Scholar 

  22. Lovász, L.: Geometry of numbers and integer programming. In: Mathematical Programming (Tokyo, 1988). Math. Appl. (Japanese Ser.), vol. 6, pp. 177–201. SCIPRESS, Tokyo (1989)

  23. Lovász, L., Schrijver, A.J.: Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  24. Maxfield, J.E., Minc H.: On the matrix equation \(X^{\prime }X = A\). Proc. Edin. Math. Soc. 13, 125–129 (1962)

    Google Scholar 

  25. Markham, T.L.: Factorizations of completely positive matrices. Proc. Camb. Philos. Soc. 69, 53–58 (1971)

    Article  MATH  MathSciNet  Google Scholar 

  26. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Math. Program. 10, 146–175 (1976)

    Article  MathSciNet  Google Scholar 

  27. Michaels, D., Weismantel, R.: Polyhedra related to integer-convex polynomial systems. Math. Program. 105, 215–232 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  28. Murty, K.G., Kabadi, S.N.: Some \({\cal NP}\)-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  29. Newman, M.: Integral Matrices. Academic Press, New York (1972)

    MATH  Google Scholar 

  30. Padberg, M.W.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139–172 (1989)

    Google Scholar 

  31. Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Glob. Optim. 7, 51–73 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  32. Rabinowitz, S.: A census of convex lattice polygons with at most one interior lattice point. Ars Comb. 28, 83–96 (1989)

    MATH  MathSciNet  Google Scholar 

  33. Ramana, M.: An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems. PhD thesis, Johns Hopkins University, Baltimore (1993)

  34. Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations. Math. Program. 124, 383–411 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  35. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)

    Google Scholar 

  36. Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1998)

  37. Saito, H., Fujie, T., Matsui, T., Matuura, S.: A study of the quadratic semi-assignment polytope. Discr. Optim. 6, 37–50 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  38. Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987)

    MATH  MathSciNet  Google Scholar 

  39. Sturm, J., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  40. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Springer, Berlin (2003)

    Google Scholar 

  41. van Emde Boas, P.: Another \({\cal NP}\)-Complete Problem and the Complexity of Computing Short Vectors in a Lattice. Technical Report 81-04, Mathematics Institute, University of Amsterdam (1981)

  42. Yajima, Y., Fujie, T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Glob. Optim. 13, 151–170 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The first author was supported by the National Science Foundation under grant CCF-0545514 and the second author was supported by the Engineering and Physical Sciences Research Council under grant EP/D072662/1. Thanks are due to two anonymous referees for their helpful corrections and suggestions.

Author information

Authors and Affiliations

  1. Department of Management Sciences, Tippie College of Business, University of Iowa, Iowa, IA, USA

    Samuel Burer

  2. Department of Management Science, Lancaster University, Lancaster, UK

    Adam N. Letchford

Authors
  1. Samuel Burer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adam N. Letchford
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Adam N. Letchford.

Additional information

Research supported in part by NSF Grant CCF-0545514.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Burer, S., Letchford, A.N. Unbounded convex sets for non-convex mixed-integer quadratic programming. Math. Program. 143, 231–256 (2014). https://doi.org/10.1007/s10107-012-0609-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0609-9

Keywords

Mathematics Subject Classification

Search

Navigation