members & address research industrial partners teaching publications gallery home page of the group
    clickable logo

Combinatorial Optimization & Graph Algorithms

TU logo

contents
.

department
 .  group
 .  .  members & address
 .  .  research
 .  .  publications
 .  .  cooperation with industry
 .  .  teaching
 .  .  .  winter term 2002/03
 .  .  .  . Lineare Optimierung
 .  .  .  .  Algorithmische Graphentheorie
 .  .  .  .  Seminar
 .  .  .  .  Diplomandenseminar
 .  .  project gallery
 .  .  events
 .  .  internals
 .  .  search

ADM II: Lineare Optimierung, Wintersemester 2002

3. Programmieraufgabe: Der Netzwerksimplex

Abgabetermin: bis 19. Februar 2003

Aufgabenstellung

Implementiert den Netzwerksimplex-Algorithmus für das verallgemeinerte Transportproblemtransshipmentproblem mit oberen und unteren Kantenkapazitäten.

Dazu lest zunächst die Beschreibung eines gerichteten Graphen aus einer Datei. Nach dem Einlesen werden die unteren Kapazitäten durch eine Transformation entfernt, so dass der Algorithmus nur noch obere Kapazitäten behandeln muß. Führt nun die Initialisierung von Phase I des Netzwerksimplex-Algorithmus durch und baut somit einen aufspannenden Baum auf. Falls der Benutzer es verlangt, sollen stets streng zulässige Baumlösungen verwaltet werden (siehe 8. Übungsblatt).

Achtung! Die Eingabegraphen sind nicht notwendigerweise zusammenhängend. Zerlegt das Problem dann in zwei oder mehr Teilprobleme und behandelt jedes Problem separat.

Überlegt euch, wie ihr den aufspannenden Baum am besten repräsentiert. Achtet dabei besonders auf gute Implementierung folgender Aspekte:

  • Neuberechnung der Knotenpotentiale bei geg. aufspannenden Baum (am Anfang von Phase I und Phase II).
  • Suche des sog. joins.
  • Suche der Pivotkanten.
  • Wie durchlaufe ich alle Knoten in dem Teilbaum unter einem bestimmten Knoten?
  • Korrektur des aufspannenden Baumes (d.h. Korrektur der Fädelung).
  • Nutzt es, die Höhe eines Knotens im Baum zu kennen?
  • Update der Knotenpotentiale.

Pivotregeln

Folgende Pivotregeln  soll Eure Implementation beherrschen:

  • Erste mögliche Kante: Wähle die erste Kante mit negativen reduzierten Kosten.
  • Zyklisch erste mögliche Kante: Wähle die erste Kante mit negativen reduzierten Kosten. Starte dabei nicht jedesmal wieder bei der ersten Kante, sondern mit der letzten davor untersuchten Kante.
  • Regel von Dantzig: Wähle die Kante mit möglichst kleinen negativen reduzierten Kosten.
  • Kandidatenliste: Halte eine Liste von Kanten mit negativen reduzierten Kosten und wähle in jedem Schritt die Kante aus der Liste mit möglichst kleinen negativen reduzierten Kosten. Wenn die Länge der Liste kleiner wird als ein gegebener Wert p, so wird sie neu berechnet. Entweder werden beim Neuberechnen alle Kanten mit negativen reduzierten Kostennegativen reduzierten Kosten eingefügt, oder nur die ersten q Kanten für ein gegebenen Wert q. (==> Übung)
Zusätzlich soll es (auf Bedarf) möglich sein streng-zulässige Basislösungen zu produzieren, d.h.  wenn eine der obigen Pivotregeln eine degenerierte Pivotkante e auswählt, wird geprüft, ob eine neue streng-zulässige Basislösung produziert werden kann. Falls dies nicht möglich ist mit der Kante e, so wird diese verworfen, d.h. nicht verwendet. Achtet bei dieser Regel darauf, daß ihr keine Endlosschleife produziert.

Die Auswahl der entsprechenden Pivotregeln soll über folgende Parameter möglich sein:


 
-s streng-zulässige Basislösungen produzieren
-e Erste mögliche Kante
-z Zyklisch erste mögliche Kante
-d Regel von Dantzig
-k Kandidatenliste

Von den Optionen -e, -z, -d und -k darf immer nur eine angegeben werden. Die Option -s kann zusätzlich angegeben werden. Wenn keine Option angegeben wird, soll als Standard -e gewählt werden.

Achtet bitte auf folgende 'Dinge':

  • Die Eingabedatei sowie weitere Optionen werden dem Programm über die Kommandozeile übergeben.
  • Trennt bitte die Algorithmen und die Daten so gut wie möglich. Implementiert den Graphen, den Baum und die Lösung x möglichst als getrennte Klassen.

    Beispiel: Es geht die Datenstruktur Graph nichts an, ob sie in einem NWSA verwendet wird oder nicht. Daher darf die Implementation der Pivotregeln nicht in der Klasse Graph erfolgen.

  • Prüft alle Invarianten sowie Pre- und Postconditions, falls die Option -c (für check) angegeben wird. (Dies ist zwar nicht Pflicht, aber ich möchte euch wärmstens empfehlen, die Tests von Anfang an mit zu implementieren, damit der Aufwand zur Fehlersuche für euch so gering wie möglich wird.)
  • Dokumentiert alles präzise.

Testdaten

... gibt es unter /homes/lop/lop-001/NetBsp.

top top
source last modified: Mon Dec 16 2002, last built: Tue Nov 25 2003
Andreas Fest; <fest@math.tu-berlin.de>
Validate HTML