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

Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

A reformulation of quadratically constrained binary programs as duals of set-copositive linear optimization problems is derived using either \(\{0,1\}\)-formulations or \(\{-1,1\}\)-formulations. The latter representation allows an extension of the randomization technique by Goemans and Williamson. An application to the max-clique problem shows that the max-clique problem is equivalent to a linear program over the max-cut polytope with one additional linear constraint. This transformation allows the solution of a semidefinite relaxation of the max-clique problem with about the same computational effort as the semidefinite relaxation of the max-cut problem—independent of the number of edges in the underlying graph. A numerical comparison of this approach to the standard Lovasz number concludes the paper.

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

Similar content being viewed by others

Notes

  1. In particular, nonnegative continuous variables are not considered here, since the nonnegativity is lost for \(\{-1,1\}\)-formulations. It is possible to extend the approach of the present paper to problems with nonnegative variables and with \(\{-1,1\}\)-variables using set-completely-positive programs with a cone \(\mathcal{{C}}_{n}^*(M)\) where \(M\) not only depends on the dimension but also on the partition of continuous and binary variables. In such generalization, also for a \(\{0,1\}\)-formulation the cone \(\mathcal{{C}}_{n}^*(M)\) will depend on the partition of continuous and binary variables, and the transformations \(T,\ \mathcal{{T}}\) of the previous section will have a block structure. For simplicity, the presentation in this paper restricts itself to plain binary problems.

References

  1. Arima, N., Kim, S., Kojima, M.: Simplified copositive and lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables, Research Report B-469. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo (2012)

  2. Benson, S.J., Ye, Y.: Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation (1999) http://www.stanford.edu/~yyye/yyye/stable.ps

  3. Bertsimas, D., Ye, Y.: Handbook of Combinatorial Optimization. Semidefinite relaxations, multivariate normal distributions, and order statistics. Kluwer Academic Publishers, Boston (1998)

    Google Scholar 

  4. Bomze, I.M., de Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163–185 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Prog. 120(2), 479–495 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  6. Dickinson, P.J., Eichfelder, G., Povh, Janez: Erratum to: on the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett. 7, 1387–1397 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  7. Eichfelder, G., Povh, Janez: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett. 7, 1373–1386 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  8. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  9. Helmberg, C.: Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21(3), 952–969 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  10. Helmberg, C., Rendl, F., Vanderbei, B., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  11. Jarre, F.: Burer’s key assumption for semidefinite and doubly nonnegative relaxations. Optim. Lett. 6(3), 593–599 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  12. Karloff, H.: How good is the Goemans-Williamson max cut algorithm? SIAM J. Comput. 29(1), 336–350 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  13. Laurent, M., Rendl, F.: Semidefinite programming and integer programming (2003) http://homepages.cwi.nl/~monique/files/chaptercwi.ps

  14. Lovasz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1–7 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  15. Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Prog. 121(2), 307–335 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  16. Tutuncu, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95, 189–217 (2003)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors would like to thank two anonymous referees for their criticism which helped to improve the presentation of the paper.

Author information

Authors and Affiliations

  1. Mathematisches Institut, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany

    Felix Lieder, Fatemeh Bani Asadi Rad & Florian Jarre

Authors
  1. Felix Lieder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fatemeh Bani Asadi Rad
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Florian Jarre
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Felix Lieder.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lieder, F., Rad, F.B.A. & Jarre, F. Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques. Comput Optim Appl 61, 669–688 (2015). https://doi.org/10.1007/s10589-015-9731-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9731-y

Keywords

Search

Navigation