Jack-III Ein Branch & Cut-Verfahren zur Lösung des gewichteten Steinerbaumproblems in Graphen

Please always quote using this URN: urn:nbn:de:0297-zib-9946
  • In der vorliegenden Arbeit werden die grundlegenden Gedanken und die Implementierung eines Branch & Cut-Algorithmus zur Lösung des gewichteten Steinerbaumproblems in Graphen beschrieben. Der Algorithmus basiert auf der linearen Relaxierung einer bidirektionalen ganzzahligen Formulierung des Problems. Wir werden das Problem einführen, drei ganzzahlige Modellierungen vorstellen, auf Reduktionsverfahren und Heuristiken eingehen sowie das Verfahren und seine Implementierung darstellen. Am Ende werden wir die Implementierung an 191 bekannten Probleminstanzen testen und auch optimale Lösungen f� ur zwei nach Wissen des Autors bis zu diesem Zeitpunkt ungelöste Instanzen liefern.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Thorsten Koch
Document Type:Master's Thesis
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:1995/12/31