MPI Informatik -> AG 1 -> Lehre -> Optimization SS 2007

Optimization - SS 2007

Instructors

Prof. Naveen Garg Building E1 4 - MPI-INF, room 315 "naveen" ät "mpi-inf.mpg.de"
Dr. Khaled Elbassioni Building E1 4 - MPI-INF, room 307 "elbassio" ät "mpi-inf.mpg.de"
Stefan Canzar Building E1 4 - MPI-INF, room 324 "scanzar" ät "mpi-inf.mpg.de"

Tutor

Mahmoud Fouz "fmahmoud" ät "mpi-inf.mpg.de"

Meeting time

Lectures: Tuesday and Thursday, 14:00-16:00, HS 003, Geb. E1 3

First class: Tuesday, 17. April 2007
Last class:     Thursday, 19. Juli 2007
Mid term Exam: Thursday, 14:00-16:00, 24 Mai, 2007
Final Exam: Thursday, 14:00-16:30, 19 Juli, 2007
Makeup Exam: Tuesday, 14:00-16:00, 25 September, 2007

Grading strategy

40 % Midterm
60 % Final

The midterm exam is OPEN BOOK OPEN NOTES
The final exam is OPEN BOOK OPEN NOTES

Text book

Intoruduction to Linear Optimization (Dimitris Bertsimas and John N. Tsitsiklis) (available in MPI library)
Final grades(Please pickup your schein from office 302)

Exercises

In Building E1 4 - MPI-INF, Room 024, Wednesdays 18:00-20:00
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Ex 6
Ex 7
Ex 8
Ex 9
Ex 10
Ex 11 (NO quiz)

Schedule (More or less, subject to changes)

17.4-19.4
  • Introduction (Chapter 1: 1.1-1.4)
    • Introduction to Linear Progamming and examples
    • Graphical representation and solution
24.4-26.4
  • Basics of LP (Chapter 2: 2.1-2.4)
    • Geomtery of Linear Programming
    • Extreme solutions, vertices, basic feasible solutions
    • Degeneracy
1.5-10.5
  • The simplex method (Chapter 3: 3.1-3.5)
    • The method and its implementation
    • Anticycling rules
    • Finding an initial BFS
15.5-17.5
  • Duality Theory (Chapter 4: 4.1-4.3)
    • The dual problem and duality Theorem
    • The dual-simplex method
22.5
  • The network flow problem (chapter 7: 7.1-7.2)
24.5
  • Midterm Exam
29.5-7.6
  • Network flow problems (Chapter 7: 7.1-7.5, 7.8)
    • The network simplex algorithm
    • The minimum cost cycle algorithm
    • The maximum flow problem
12.6-14.6
  • Integer programming (Chapters 10, 11: 11.1-11.2)
    • Integer programming formulations
    • Cutting plane methods
    • Branch and bound
21.6-28.6
  • The Ellipsoid method (Chapter 8)
    • The Ellipsoid algorithm
    • Problems with exponentially many constraints
3.7-10.7
  • Interior point methods (Chapter 9: 9.1-9.2)
    • The affine scaling algorithm
    • Karmarkar's algorithm
12.7
  • Advanced topics (TBA but can be a subset of the following)
    • Total unimodularity and its applications in Combinatroial Optimization (Chapter 7)
    • Approximation algorithms (Chapter 11: 11.5)
17.7
  • Some Exercises (including Bimatrix games)
19.7
  • Final Exam
25.9
  • Makeup Exam
    WWW page maintained by Khaled Elbassioni, last updated on Monday, 18 June 2007