Publikation: A Branch and Bound Algorithm for Max-Cu...

Stammdaten
Titel: A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
Untertitel:
Kurzfassung: In this paper we present a method for finding exact solutions of the Max-Cut problem max x'Lx such that x ∈ { − 1,1}^n. We use a semidefinite relaxation combined with triangle inequalities, which we solve with the bundle method. This approach is due to Fischer, Gruber, Rendl and Sotirov and uses Lagrangian duality to get upper bounds with reasonable computational effort. The expensive part of our bounding procedure is solving the basic semidefinite programming relaxation of the Max-Cut problem. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to unconstrained quadratic 0-1 problems and to instances of the graph bisection problem. The experiments show, that our method nearly always outperforms all other approaches. Our algorithm, which is publicly accessible through the Internet, can solve virtually any instance with about 100 variables in a routine way.
Schlagworte:
Publikationstyp: Beitrag in Sammelwerk (Autorenschaft)
Erscheinungsdatum: 06.2007 (Print)
Erschienen in: Integer Programming and Combinatorial Optimization
Integer Programming and Combinatorial Optimization
zur Publikation
 ( Springer; R.E. Bixby, E.A. Boyd, R.Z. Rios-Mercado )
Titel der Serie: Lecture Notes in Computer Science
Bandnummer: -
Erstveröffentlichung: Ja
Seite: S. 295 - 309

Versionen
Keine Version vorhanden
Erscheinungsdatum: 06.2007
ISBN:
  • 9783540727910
ISSN: 03029743
Homepage: http://www.springerlink.com/content/u11k527t13322107/?p=b12d2a0a88054528bf5badcd97ba8596&pi=0

AutorInnen
F. Rendl
Keine Daten vorhanden
*
G. Rinaldi
Keine Daten vorhanden
*
A. Wiegele
Keine Daten vorhanden
*
Franz Rendl
Franz.Rendl@aau.at
Forschungsaktivitäten
zur Visitenkarte
(intern)
Angelika Wiegele
angelika.wiegele@aau.at
Institut für Mathematik
Forschungsaktivitäten
zur Visitenkarte
(intern)

Zuordnung
Organisation Adresse
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Kategorisierung
Sachgebiete
  • 1104 - Angewandte Mathematik
  • 1121 - Operations Research (5347, 5919)
Forschungscluster Kein Forschungscluster ausgewählt
Peer Reviewed
  • Ja
Publikationsfokus
  • Science to Science (Qualitätsindikator: n.a.)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt

Kooperationen
Keine Partnerorganisation ausgewählt

Beiträge der Publikation
Keine verknüpften Publikationen vorhanden