Computational Mixed-Integer Semidefinite Programming

Die semidefinite Programmierung mit gemischten ganzen Zahlen (MISDP) war in den letzten Jahren ein aktives Forschungsgebiet. MISDP-Formulierungen tauchten in vielen verschiedenen Anwendungen auf und wurden häufig durch problemspezifische Lösungsansätze angegangen. Im Gegenteil, es gibt immer noch einen gravierenden Mangel sowohl an theoretischen als auch an Software-Implementierungen für die allgemeine semidefinite Programmierung mit gemischten ganzen Zahlen. Diese Arbeit behandelt beide Themen, insbesondere die Beibehaltung einer starken Dualität und entsprechende Einschränkungsqualifikationen bei Relaxationen der semidefiniten Programmierung (SDP) nach variablen Verzweigungen. Da dies Anforderungen für die Konvergenznachweise von Innenpunktlösern sind, die zur Lösung der Teilprobleme verwendet werden, sind diese auch für die Richtigkeit eines SDP-basierten Branch-and-Bound-Algorithmus erforderlich. Auf der Implementierungsseite werden viele verschiedene Verbesserungen eingeführt, die im MISDP-Solver SCIP-SDP implementiert sind. Insbesondere werden die Erzeugung von Schnittebenen, eine auf konischer Dualität basierende Ausbreitungstechnik, Warmstarttechniken für SDP-Löser mit Innenpunkten und spezielle Schnitte für SDP-Rucksäcke, bei denen es sich um MISDPs handelt, bei denen alle Beschränkungsmatrizen positiv semidefinit sind, diskutiert. Schließlich werden numerische Ergebnisse für mehrere Anwendungen vorgestellt, insbesondere das robuste Design der Fachwerktopologie. Dies zeigt, dass SCIP-SDP derzeit einer der schnellsten Löser für die semidefinite Programmierung mit gemischten Ganzzahlen ist.