Titel Englisch: Discrete optimization

Bereich: Ba Aufbaubereich

Wahlpflichtmodul

Schwerpunkt: Optimierung

ESSEN

Studierbar ab Fachsemester: B5

ECTS-Punkte: 9,

Prüfungsform: Die ECTS-Punkte werden auf Grund einer mündlichen Prüfung innerhalb von drei der Veranstaltung folgenden Monaten vergeben. Innerhalb von sechs Monaten nach der Prüfung besteht Möglichkeit zur Nachprüfung. Die Prüfungsleistung wird benotet. Die Lehrenden werden die Modalitäten der Prüfung zu Beginn der Veranstaltungen festlegen.

Sprache: In der Regel Deutsch.

Verantwortlich:
Prof. Dr. Rüdiger Schultz.

Angebotsturnus:
WS, nicht jährlich

Diskrete Optimierung

Vorlesung/4 SWS und Übung/2 SWS

Inhalt

  • Schranken, Relaxationen, Dualität,
  • Ganzzahlige Polyeder, Totale Unimodularität,
  • Matchings,
  • Dynamische Optimierung,
  • Branch-and-Bound,
  • Schnittebenenalgorithmen,
    Eines der folgenden drei Themen:
  • Spaltengenerierungsalgorithmen,
  • Primale Suchalgorithmen,
  • Grundlagen der Komplexitätstheorie.

Lernziele

Es werden spezielle Kenntnisse zur Theorie und Algorithmik der diskreten, insbesondere der ganzzahligen und kombinatorischen linearen Optimierung vermittelt. Ein breites Verständnis der Methodiken auf Grundlage relevanter Sachverhalte aus diskreter Mathematik, Graphentheorie und Analysis soll sich ausprägen.. Des weiteren erlernen die Teilnehmer Modellierungstechniken, Algorithmenentwurf, -auswahl und -implementierung, wobei letzteres die Arbeit mit Spezialsoftware einschlie{\ss}t.

Literatur

  • Bertsimas, Weismantel: Optimization over Integers, Dynamic Ideas, 2005.
  • Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization. Wiley 1998
  • Korte, Vygen: Combinatorial Optimization. Springer 2000
  • Nemhauser, Wolsey: Integer and Combinatorial Optimization. Wiley 1988
  • Schrijver: Theory of Linear and Integer Programming. Wiley 1998
  • Schrijver: Combinatorial Optimization, Polyhedra and Efficiency, Volumes A-C, Springer, 2003.
  • Wolsey: Integer Programming. Wiley 1998

Weitere Literatur wird in den Veranstaltungen bekanntgegeben.

Arbeitsaufwand

270 Stunden (davon 90 Stunden Präsenz)