Kürzeste Wege mit Nebenbedingungen und verwandte Probleme

einen Pfad minimaler Kosten zwischen zwei Knoten eines Graphen
sucht, ist effizient in polynomieller Zeit lösbar.
In vielen praktischen Anwendungen wollen wir jedoch, dass
ein Pfad bestimmte Budget- oder Resourcenbedingungen erfüllt.
Dies ist das Kürzeste-Wege-Problem mit Nebenbedingungen, das zur
Klasse der ``schweren'' Probleme gehört, für die wir keinen
polynomiellen Algorithmus kennen.
In diesem Vortrag stellen wir eine 2-Schritt-Methode für das
Kürzeste-Wege-Problem mit Nebenbedingungen vor.
Wir lösen zuerst eine Relaxierung
des Problems und erhalten eine obere und untere Schranke, um dann
durch Schließen der Lücke durch geschicktes Auflisten von Pfaden
das Optimum zu bestimmen. Wir vergleichen bekannte und neue Verfahren
sowohl theoretisch als auch experimentell.
Die 2-Schritt-Methode ist auch auf eine allgemeinere Klasse von
Netzwerkoptimierungsproblemen mit Nebenbedingungen anwendbar.
Wir illustrieren die generische Methode anhand einiger Beispiele.
Danach stellen wir unser Softwarepaket CNOP vor, das dieses
generische Verfahren implementiert.