Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (Articolo in rivista)

Type
Label
  • Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (Articolo in rivista) (literal)
Anno
  • 2010-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/s10107-008-0235-8 (literal)
Alternative label
  • Rendl, F.; Rinaldi, G.; Wiegele, A. (2010)
    Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations
    in Mathematical programming
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Rendl, F.; Rinaldi, G.; Wiegele, A. (literal)
Pagina inizio
  • 307 (literal)
Pagina fine
  • 335 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 121 (literal)
Rivista
Note
  • Google Scholar (literal)
  • ISI Web of Science (WOS) (literal)
  • Mathematical Reviews on the web (MathSciNet) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • F. Rendl; A. Wiegele: Alpen-Adria-Universität Klagenfurt, Institut für Mathematik, Universitätsstr. 65-67, 9020 Klagenfurt, Austria (literal)
Titolo
  • Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (literal)
Abstract
  • We present a method for finding exact solutions of Max-Cut, the problem of finding a cut of maximum weight in a weighted graph. We use a Branch-and-Bound setting that applies a dynamic version of the bundle method as bounding procedure. This approach uses Lagrangian duality to obtain a \"nearly optimal\" solution of the basic semidefinite Max-Cut relaxation, strengthened by triangle inequalities. The expensive part of our bounding procedure is solving the basic semidefinite relaxation of the Max-Cut problem, which has to be done several times during the bounding process. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to instances of unconstrained quadratic 0-1 optimization and to instances of the graph equipartition problem. The experiments show that our method nearly always outperforms all other approaches. In particular, for dense graphs, where linear programming-based methods fail, our method performs very well. Exact solutions are obtained in a reasonable time for any instance of size up to n = 100, independent of the density. For some problems of special structure we can solve even larger problem classes. We could prove optimality for several problems of the literature where, to the best of our knowledge, no other method is able to do so. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it