Arbeitsgruppe Algorithmen und Komplexität

Zweiter CAU-FLS-Programmierwettbewerb

Wir richten zum zweiten Mal in Kooperation mit der der Heikendorfer Softwarefirma FLS einen Programmierwettbewerb aus. Es wird ein Optimierungsproblem aus der Routenplanung vorgestellt, das von den Teilnehmern gelöst werden soll. Die Programme der Teilnehmer werden in mehreren Kategorien bewertet. Insgesamt werden Preisgelder in Höhe von 4.500 € vergeben, die FLS stiftet.

Bester Vortrag

Die Teilnehmer stellen ihre Algorithmen in einem Kurzvortrag vor. Für die beste Präsentation sind 500 € ausgelobt.

Beste Algorithmen-Idee

Anhand der Vorträge werden die Ideen hinter den Algorithmen in Hinblick auf Einfallsreichtum und Qualität bewertet. Die beste Idee wird mit 500 € prämiert.

Lösungsqualität

Die Programme werden live mit den gleichen Daten getestet. Die Ersteller der drei besten Programme erhalten jeweils 2.000 €, 1.000 € bzw. 500 €.

Problembeschreibung

Das zu lösende Problem ist die Planung eines Pizzalieferdienstes. Eine genaue Beschreibung gibt es als PDF zum herunterladen.

Datei mit Fahrzeiten und Fahrtkosten
Kleiner Datensatz zum Testen

Die Programme werden durch ein Auswertungsprogramm automatisch gestartet und bewertet. Es ist in Python 2.7 geschrieben und unterstützt Linux. Das Archiv enthält auch einige triviale Beispielprogramme. Hier eine Beispielsitzung, in der eine Testinstanz generiert und bewertet wird:

boromir{fku} python generate-instance.py
usage: generate-instance.py [-h] datafile start end k outfile
generate-instance.py: error: too few arguments
boromir{fku} python generate-instance.py data/data.txt 12:00 14:00 50 instance.txt
boromir{fku} python evaluate.py
usage: evaluate.py [-h] datafile instance ...
evaluate.py: error: too few arguments
boromir{fku} python evaluate.py data/data.txt instance.txt python bad_program.py
12:00:00.000 Simlation started with 0 vehicles
12:08:01.000 Received order 1 274 12:08:01 12:53:01 10 5.21 17.37
12:09:01.000 No response for order 1
12:09:01.000 Simlation ended with disqualification

Teilnahmebedingungen

Teilnehmen dürfen alle Studierende des Instituts für Informatik, ausgenommen Promotionsstudierende. Eine Anmeldung ist nicht erforderlich. Es wird ein Optimierungsproblem gestellt, das einzeln oder in Gruppen gelöst werden kann.

Zwischenrunde

Am 09.01. 2015 werden die maximal 10 Teilnehmer der Endrunde bestimmt und benachrichtigt. Bewertet wird nach Qualität der ausgegebenen Lösungen. Berücksichtigt werden alle funktionsfähigen Programme, die bis 12:00 per Email bei Felix Land. eingehen.

Endrunde

Die Endrunde findet nur statt, wenn sich mindestens 8 Teilnehmer in der Zwischenrunde für die Teilnahme qualifiziert haben. diese Teams haben noch bis zur Endrunde Zeit, ihr Programm weiter zu verbessern. Mindestens ein Gruppenmitglied muss das Programm bei der Endrundenveranstaltung präsentieren. Die Programme werden dann live mit den gleichen Daten getestet.

Bewertung der Programme

Die Programme werden auf einem Projektrechner (Linux) der Arbeitsgruppe bewertet. Sie können in einer beliebigen darauf zur Verfügung stehenden Programmiersprache geschrieben sein. Der Wettbewerbsrechner wird so konfiguriert, dass nur ein Prozessorkern genutzt wird. Als gemeinsames Interface wird die Standard-Ein/Ausgabe genutzt. Das Datenformat und einige Testinstanzen werden mit Wettbewerbseröffnung zur Verfügung gestellt.

Der Projektrechner wird den Teilnehmern zugänglich gemacht, sodass sie ihre Programme testen können. Die Teilnehmer können natürlich auch zuhause entwickeln, wir stellen ihnen dazu auf Wunsch CPLEX in der akademischen Lizenz für die gängigen Plattformen zur Verfügung. Hinweise zur Verwendung von CPLEX gibt es auf unserer Anleitungsseite.

Termine

Vorstellung der Wettbewerbsaufgabe

Dienstag 04.11. 2014
12:15 Uhr
Wilhelm-Seelig-Platz 3, Seminarraum 2
Die Beschreibung gibt es dann auch auf dieser Webseite

Zwischenrunde

Freitag 09.01. 2015 12:00 Uhr

Endrunde

Montag 30.03. 2015 in den Räumlicheiten von FLS in Heikendorf

Kontakt und Anmeldung

Allen Teilnehmern wird empfohlen, sich bei Felix Land anzumelden. Dadurch können sie über Neuigkeiten informiert werden.