Lineare Optimierung 2008 - Programmieraufgabe

Sie sollen das Verfahren von Fourier-Motzkin zur Elimination von Variablen in einem Ungleichungssystem der Form Ax<=b in C implementieren. Dazu dürfen Sie eine von uns bereitgestellte Bibliothek von Routinen zur Matrix- und Vektorverwaltung und Ein-/Ausgabe benutzen.

Die Abnahme dieser Programmieraufgabe erfolgt in mehreren Etappen:

0. Etappe (zu bearbeiten bis 10. April 2008)

Machen Sie sich mit der Bibliothek fmlib vertraut. Das Headerfile fmlib.h enthält die Strukturdefinitionen und die Prototypen aller für Sie bereitgestellten Funktionen sowie deren Dokumentation.

Das Headerfile liegt auf unserem Rechner im Verzeichnis /home/lop/include/; in Ihr C-Programm wird es mittels

  #include "fmlib.h"

eingebunden.

Wenn Sie Ihr Programm compilieren (genauer: linken), müssen Sie zusätzlich die Bibliotheksdatei /home/lop/lib/libfmlib.a einbinden, indem Sie die Optionen -lfmlib -lgmp an cc übergeben.

Schreiben Sie unter Verwendung dieser Bibliothek ein Programm, das ein Ungleichungssystem im IEQ-Format aus einer Datei einliest, in einer Poly-Struktur speichert und gleich wieder im IEQ-Format ausgibt. Das IEQ-Format ist auf einer UNIX-Manpage dokumentiert (man ieq).

Beachten Sie, daß die Einlesefunktion (readPoly) IEQ-Format versteht, die Ausgabefunktionen (printPoly, fprintPoly) aber kein IEQ-Format, sondern ein Phantasieformat erzeugen. Sie müssen also noch eine Ausgabefunktion schreiben, die tatsächlich IEQ-Format erzeugt.

1. Etappe (zu bearbeiten bis 22. Mai 2008)

Als ersten Teilschritt soll Ihr Programm eine gegebene Variable eliminieren und das hierbei entstehende Ungleichungssystem ausgeben.

Schreiben Sie dazu eine Funktion mit folgendem Prototypen:

  Poly FMElim(Poly P, int idx);

Das heißt: Sie bekommen ein Polyeder P, einen Variablenindex und liefern ein neu erzeugtes Polyeder, das durch Elimination der Variable mit diesme Index zurück.

Ihr Programm sollte gut dokumentiert sein. Sie dürfen selbstverständlich eigene Hilfsfunktionen definieren.

2. Etappe (zu bearbeiten bis 12. Juni 2008)

Programmieren Sie das Verfahren von Fourier-Motzkin zur Elimination von Variablen in einem Ungleichungssystem. Hier soll Ihr Programm sukzessive eine durch eine Liste gegebene Teilmenge der Variablen eliminieren und die hierbei entstehenden Ungleichungssysteme ausgeben.

Ihr Programm soll von der Kommandozeile den Namen einer Datei im IEQ-Format sowie die Indizes der zu eliminierenden Variablen lesen und die Ungleichungsbeschreibung des projizierten Polyeders in die Standardausgabe schreiben.

Versuchen Sie, nach jedem Eliminationsschritt redundante Ungleichungen zu entfernen.

Testen Sie Ihr Programm an den Beispielen, die Sie im Verzeichnis /home/lop/share/examples/ finden. Stellen Sie sicher, dass Ihr Programm bei unsinnigen Eingaben und in Ausnahmesituationen vernünftige Fehlermeldungen ausgibt.

Zum Vergleich können Sie die in PORTA implementierte Fourier-Motzkin-Elimination verwenden. Lesen Sie hierzu die UNIX-Manpage (man fmel).