Programmierpraktikum Optimierung WS 15/16

Inhalt:

• Meisterschaftsproblem (Sportligen)
  

  

  Gegeben: eine aktuelle Tabelle einer Liga sowie ein Spielplan der restlichen Spiele.
  Frage: Wer kann noch Meister werden?
  Je nach Punktevergabe in der Liga ist dieses Problem effizient exakt lösbar bzw. NP-vollständig.
  Es sollen verschiedene Verfahren (exakt und heuristisch) implementiert und getestet werden.

• Verschnitt-/Packprobleme
  

  

  Gegeben: zweidimensionale rechteckige Objekte, die aus größeren Platten herausgeschnitten werden sollen.
  Aufgabe: Bestimme Schnittmuster, so dass der Verschnitt minimiert wird.
  Es sollen verschiedene heuristische Verfahren implementiert und an Praxisdaten getestet werden.

Termine:

3-wöchiges Blockpraktikum in der VL-freien Zeit:

Literatur

• Bernholt, T., Gülich, A., Hofmeister, T., Schmitt, N., Wegener, I. [2002]: Komplexitätstheorie, effiziente Algorithmen und die Bundesliga. Informatik-Spektrum, 25(6), 488-502.
• Bernholt, T., Gülich, A. [2000]: Anwendung von Komplexitätstheorie und Effizienten Algorithmen auf die Fußballbundesliga. Diplomarbeit, Universität Dortmund.
• Adler, I., Erera, A. L., Hochbaum, D. S., Olinick, E. V. [2002]: Baseball, optimization, and the world wide web. Interfaces, 32(2), 12-22.
• Ribeiro, C.C., Urrutia, S. [2005]: An application of integer programming to playoff elimination in football championships. International Transactions in Operational Research, 12(4), 375-386.
• Wäscher, G., Haußner, H., Schumann, H. [2007]: An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109-1130.
• Berkey, J.O., Wang, P. Y. [1987]: Two-dimensional finite bin-packing algorithms. Journal of the Operational Research Society 38(5), 423-429.
• Lodi, A., Martello, S., Vigo, D. [2002]: Recent advances on two-dimensional bin packing problems. Discrete Applied Mathematics 123(1), 379-396.
• Lodi, A., Martello, S., Vigo, D. [1999]: Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing 11(4), 345-357.
• Instanzen 2DPackLib

Teilnahme

Teilnehmen können alle interessierten Bachelor-Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science. Die Veranstaltung zählt als Programmierpraktikum (P4 / 6 LP).

Vorkenntnisse

Von den Teilnehmern werden erwartet:

• Programmierkenntnisse in Java (wie sie z.B. durch Informatik A und B vermittelt werden)
• Grundlagen von Algorithmen und Datenstrukturen

Kenntnisse aus dem Bereich der kombinatorischen Optimierung sind nützlich, aber nicht unbedingt Voraussetzung für eine Teilnahme.

Schein