Solving the multi-objective Steiner Tree problem with resources

Abstract

Netzwerkentwurfsprobleme bilden eine Klasse von kombinatorischen Optimierungsproblemen, deren Anwendungsgebiete vom Entwurf von Telekommunikationsnetzwerken bis zur Planung von städtischer Infrastruktur reichen. Ein bekanntes Problem dieser Klasse ist das NP-schwere Steinerbaumproblem auf Graphen (STP), welches darin besteht, den kostengünstigsten Teilbaum des Eingangsgraphen zu finden, der alle Knoten aus der gegebenen Menge an Terminalknoten verbindet. In real auftretenden Problemen ist es jedoch oft nötig, Lösungen anhand mehrerer Gesichtspunkte zu bewerten. Um die Modellierung solcher Probleme zu ermöglichen, definieren wir das Multikriterielle Steinerbaumproblem mit Ressourcen (MOSTPR), welches eine Generalisierung des einfachen STP auf mehrere Zielfunktionen ist, bei dem jeder Kante zusätzlich eine Menge an Ressour- cen, die sie verbraucht, zugeteilt ist. Unsere zusätzlichen Ziele sind, den maximalen Gesamt- verbrauch jeder einzelnen Ressource entlang der Pfade vom Wurzel- zu den Terminalknoten zu minimieren. Zur Lösung der Problemvariante mit zwei Zielfunktionen (BOSTPD) entwickeln wir auf der --Constraint Methode basierende Algorithmen, welche die Instanz in Teilinstanzen mit nur einer Zielfunktion (RDCSTP) zerlegen, diese gemäß zweier ILP-Formulierungen codieren und mittels Branch-and-Cut lösen. Da die Algorithmen nur exakte Verfahren verwenden, können wir mit ausreichend Zeit und Speicher die vollständige Paretofront finden. Um die Laufzeit der Algorithmen zu verbessern, entfernen wir vor Beginn jeder Iteration alle Knoten und Kanten, die nicht Teil einer optimalen Lösung sein können. Weiters verwenden wir Informationen aus vorhergehenden Iterationen, wie etwa deren optimale Lösung oder mittels Branch-and-Cut hinzugefügte Ungleichungen, zur Beschleunigung des Lösungsvorgangs. Wir testen die Implementierung der zuvor erwähnten Algorithmen auf einer Reihe von Bei- spielinstanzen. Diese Tests zeigen, dass nicht nur die Größe einer Instanz, sondern auch ihre Struktur einen starken Einfluss auf die Laufzeit hat, die zum Berechnen der Paretofront nötig ist. Weiters zeigen wir, dass sowohl das Entfernen überflüssiger Knoten und Kanten als auch die Wiederverwendung von Information aus Voriterationen die benötigte Laufzeit stark reduzieren können. Abschließend beschreiben wir, wie die von uns für das BOSTPD entwickelten Algorithmen modifiziert werden können, um das allgemeine Problem mit beliebiger Anzahl an Ressourcen zu lösen. Wir weisen dabei auch auf die zu erwartenden Probleme hin, die derartige Modifikationen mit sich bringen können, wie etwa die größere Anzahl an zu lösenden Teilproblemen und deren höhere Schwierigkeit.

Network design problems are an important class of combinatorial optimization problems, with applications ranging from the design of telecommunication networks to the planning of a city-s street and power grid. One of these problems is the Steiner Tree Problem on Graphs (STP), a well-known NP-hard combinatorial optimization problem that consists in finding a subgraph of the given input graph that connects a given subset of its vertices, the set of terminal vertices, as cheaply as possible. In real-world problems, however, it is often important to consider further attributes when evaluating a solution. To allow for the modeling of such problems, we define the Multi-objective Steiner Tree Problem with Resources, which is a multi-objective generalization of the STP. Given a set of resource demands associated with each edge, the problem not only seeks to minimize a solution-s cost, but also the maximum of each resource-s cumulative consumption along each path between the root and a terminal vertex. We develop a series of algorithms for solving the bi-objective variant of this problem, the so-called Bi-objective Steiner Tree Problem with Delays. These algorithms use the --constraint method to decompose the bi-objective input instance into a series of instances of the single- objective Rooted Delay-constrained Steiner Tree Problem. To solve these, we encode them as integer linear programs according to the formulations developed for this problem, which are then solved by branch-and-cut. Since we only use exact methods, our algorithms compute the exact Pareto frontier of our original instance, given enough time and memory. To improve the performance of our algorithms, we preprocess the subproblem graphs before each iteration. Additionally, we reuse information from previous iterations, such as optimal solutions and inequalities added by branch-and-cut, during subsequent ones. To enable the reuse of solutions that are no longer feasible for the next iteration, we develop a heuristic to transform them into feasible ones. We test our implementations of the developed algorithms on a set of benchmark instances. These tests show that in addition to an instance-s size, its structure (i.e., how an edge-s cost and delay are determined) can have a significant impact on the time necessary to find its complete Pareto frontier. The tests also show that preprocessing and the reuse of information both have an often quite significant positive impact on the performance of our algorithms. Finally, we describe how the aforementioned algorithms for the bi-objective case can be adapted to solve the multi-objective problem. We note, however, that the generalization towards multiple objectives introduces significant challenges, including the problem of finding a suitable starting point for the --constraint method, the large number of subproblem instances that need to be solved and the likely high difficulty of solving these instances.