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.
| Author: | Thorsten KochORCiD |
|---|---|
| Document Type: | Master's Thesis |
| Publishing Institution: | Zuse Institute Berlin (ZIB) |
| Date of first Publication: | 1995/12/31 |
