-

 

 

 




Optimization Online





 

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

Felix Lieder (lieder***at***opt.uni-duesseldorf.de)
Fatameh Bani Asadi Rad Rad (f.baniasadirad***at***yahoo.com)
Florian Jarre (jarre***at***opt.uni-duesseldorf.de)

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.

Keywords: Max-cut relaxation, max-clique problem, semidefinite program, completely positive program, set-copositive, binary, randomization techniques

Category 1: Combinatorial Optimization

Category 2: Integer Programming (0-1 Programming )

Citation: Lieder, F., Rad, F. B. A., & Jarre, F. (2015). Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques. Computational Optimization and Applications, 61(3), 669-688.

Download:

Entry Submitted: 04/17/2014
Entry Accepted: 04/18/2014
Entry Last Modified: 11/14/2016

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society