Branch-and-price for the Steiner tree problem with revenues, budget and hop constraints

Abstract

Diese Diplomarbeit behandelt das Steiner tree problem with revenues, budget and hop constraints (STPRBH), ein NP-schweres kombinatorisches Optimierungsproblem mit Anwendungen unter anderem im Design von Telekommunikationsnetzen. Eine Instanz des STPRBH besteht aus einem ungerichteten Graphen mit einem Wurzelknoten, Knoten, die nicht-negativen Ertrag generieren, falls sie in einer Lösung mit dem Wurzelknoten verbunden sind und Kanten mit positivem Gewicht. Weiters ist ein Budget B und ein Hoplimit H Teil einer Instanz. Erlaubte Lösungen sind alle Steiner-Bäume dieses Graphen, die den Wurzelknoten enthalten und in denen jeder Pfad vom Wurzelknoten bis zu einem anderen Knoten im Baum höchstens aus H Kanten besteht. Weiters darf die Summe der Gewichte der Kanten im Baum höchstens B betragen. Ziel ist es, eine gültige Lösung mit möglichst hohem Gewinn, der durch die Summe der Erträge der in der Lösung vorhandenen Knoten definiert ist, zu finden.<br />Es werden mehrere Formulierungen für das STPRBH als ganzzahliges lineares Programm (ILP) mit exponentiell vielen Variablen vorgeschlagen.<br />Außerdem werden branch-and-price Verfahren, die auf diesen Formulierungen basieren und das exakte Lösen von Instanzen des STPRBH erlauben, eingeführt. Bei der Anwendung dieser branch-and-price Ansätze in der Praxis treten aber verschiedenste Probleme auf. Deshalb wird die Anwendbarkeit verschiedener Möglichkeiten deren Effizienz zu verbessern analysiert. Diese Möglichkeiten umfassen Stabilisierungstechniken, verschiedene Pricing-Strategien und Heuristiken, um Startlösungen zu generieren.<br />Tests auf schon existierenden Benchmark-Instanzen zeigen, dass die vorgeschlagenen branch-and-price Ansätze kompetitiv mit schon existierenden exakten Verfahren, die auf branch-and-price basieren, sind, falls das Hoplimit oder die Anzahl der Knoten mit positivem Ertrag vergleichsweise klein ist. In Instanzen, in denen das Budget B keine Rolle spielt (d.h. hoch genug ist, um keine Einschränkung darzustellen), sind die branch-and-price Verfahren sogar meist klar besser als die branch-and-cut Verfahren. Es muss aber beachtet werden, dass diese spezifische Variante des STPRBH nicht NP-schwer ist. Für Instanzen mit großem Hoplimit oder einer großen Anzahl von Knoten mit positivem Ertrag sind die vorgeschlagenen branch-and-price Verfahren noch nicht kompetitiv mit den branch-and-cut Verfahren. Durch die implementierten Stabilisierungsmethoden und Beschleunigungsmethoden wurde aber eine signifikante Beschleunigung der branch-and-price Verfahren erreicht.