Lecture: Computational Integer Programming (ADM III)

To the Institute for Mathematics

Winter Semester 2011

LV-Nr.: 3236 L 231

PD Dr. habil. Ralf Borndörfer (www)    und     Dr. Thorsten Koch (www)

News (down)   Content (down)   Prerequisites (down)   Timing (down)   Further Information (down)   References (down)   Downloads (down)   Contact (down)

News (up)

Downloads (up)

Content (up)

How do you solve a combinatorial optimization problem? This integrated lecture offers a guide to the use and the implementation of modern computer oriented solution methods of integer programming at the example of the travelling salesman problem and the Steiner tree problem. Choosing a suitable model, preprocessing, deriving lower and upper bounds by relaxations, heuristics, and approximation methods as well as the separation and application and of cutting planes in branch-and-cut methods are covered. The application of these techniques is trained in the exercise part using advanced software tools such as Zimpl and SCIP.

Wie löst man ein kombinatorisches Optimierungsproblem? In dieser integrierten Veranstaltung werden moderne computerorientierte Lösungsmethoden der ganzzahligen Optimierung am Beispiel des Traveling-Salesman-Problems und des Steinerbaumproblems vorgestellt, implementiert und erprobt. Die Auswahl einer geeigneten Modellierung, Preprocessing, die Konstruktion von unteren und oberen Schranken durch Relaxierungen, Heuristiken und Approximationsmethoden sowie die Verwendung von Schnittebenen in Branch-and-Cut-Verfahren und deren Separierung werden behandelt. Die Techniken werden im Übungsteil mit Hilfe von geeigneten Softwaretools wie Zimpl und SCIP angewendet.

Prerequisites (up)

Knowledge in Computer Oriented Mathematics (COMA), Linear Algebra (LA), Combinatorial, Linear, and Integer Programming (ADM I und II).

Timing (up)

The lecture takes place

Further Information (up)

This lecture is classified as ADM III with 10 credit points and as an advanced Berlin Mathematical School (BMS) course.

Criteria for certificate aquisition: Here you find the lecture's entry in the university calendar of TU Berlin and in the BMS calendar.

References (up)

Contact (up)

Office Hours
Room Fon Email
PD Dr. habil. Ralf Borndörfer (www) on appointment ZIB 84185-243 borndoerferzib.de
Dr. Thorsten Koch (www) on appointment ZIB 84185-213 kochzib.de

Last update: February 06, 2012