SR 911

Dieser Vortrag handelt von einer exakten Lösungsmethode des Max-Cut Problems, ein NP-schweres kombinatorisches Optimierungsproblem. Grundlage dieses neuen Algorithmus ist ein Semidefinites Optimierungsproblem (SDO), dessen Lösung als obere Schranke an den maximalen cut verwendet wird. Da das Lösen dieses Semidefiniten Optimierungsproblems auf Grund der vielen Nebenbedingungen mit herkömmlichen Methoden nicht möglich ist, verwenden wir die sogenannte Bundle Methode, um das Problem `fast` optimal zu lösen. Diese Schrankenberechnung wird in einem Branch and Bound Verfahren eingebaut und all das zusammen nennen wir Biq Mac - a solver for BInary Quadratic and MAx-Cut problems. Im Vortrag wird das Max-Cut Problem erklärt und das SDO hergeleitet. Weiters wird die Bundle Methode, mit der das SDO gelöst wird, erläutert. Es werden viele numerische Resultate präsentiert und wir geben eine grobe Übersicht, wie sich die Rechenzeiten von Biq Mac mit jenen anderer exakter Lösungsmethoden vergleichen lassen.

Frau Dr. Angelika Wiegele

Universität Köln