direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Introduction to Linear and Combinatorial Optimization (ADM I)

News

  • (2012/02/17) Thanks for this fun semester, and all the best for your oral exams!
  • (2012/02/17) Congratulations to groups 112 and 128 for winning the competition.

  • (2012/02/17) Scheine are ready in the secretary.

  • (2012/01/25) Starting with today you can reserve a date and time for the oral exam for ADM I (Feb 23+24 and March 5+6). (There is a choice whether you do the exam for ADM I & II separately or combined. Check your Pr├╝fungsordnung.) We expect you to hand in your P├╝fungszettel at least one week before the exam.

  • (2012/01/25) The slides from Jan 20 have again been updated. Check the comments below for more information.

  • (2012/01/25) The upcoming week (Jan 30 to Feb 3) there will be no lecture. However, we move the exercise session from Friday to Thursday. Hope to see you then!

  • (2011/12/09) The oral ADM I exams will take place on Feb 23 and 24 and March 5 and 6. Further informations will follow.

  • (2011/11/30) The current version of eclipse (indigo) in the unixpool is not able to run SVN from within the IDE. Thanks to Robert Rudow there is a fully functionable version available:

    /net/co1/test_eclipse_indigo/eclipse/eclipse

  • Welcome! This is the webpage of the newly created course ADM I taught by Prof. Skutella. Please be aware that the contents of the lectures ADM I + II have changed according to this description.

Contact Information

room
phone
e-mail
office hours
Lecturer
Prof. Dr. Martin Skutella
MA 521
(030) 314-28641

Tuesday 14-15
Assistant
Madeleine Theile
MA 516
(030) 314-78650

by appointment
Student Assistant
Steffen Suerbier
MA 515

Complete the e-mail addresses by adding 'at'math.tu-berlin.de.



Schedule



Weekday
Hour
Room
Lecture
Wednesday
10 - 12
MA 041
Lecture
Thursday
16:05 - 17:35
MA 043
Exercise Session
Friday
14 - 16
MA 041
Tutorial Session 1 (in German)
Monday
14 - 16
MA 750
(Nov 28: in MA 313)
Tutorial Session 2 (in English)
Thursday
10 - 12
BMS seminar room, 2nd floor
Lecture
Tuesday October 25 and November 1
16 - 18
MA 041
Priority time
 
  • Monday 16-18
  • Tuesday 16-18
  • Wednesday 14-18
  • Thursday 12-16
    •  

Unixpool

Slides and Lecture Notes

  1. Lecture 20/10/2011: slides, notes b/w, notes col
  2. Lecture 21/10/2011: slides, notes b/w, notes col
  3. Lecture 25/10/2011: slides, notes b/w, notes col
  4. Lecture 26/10/2011: slides, notes b/w, notes col
  5. Lecture 27/10/2011: slides, notes b/w, notes col
  6. Lecture 01/11/2011: slides, notes b/w, notes col
  7. Lecture 02/11/2011: slides, notes b/w, notes col
  8. Lecture 03/11/2011: slides, notes b/w, notes col
  9. Lecture 10/11/2011: slides, notes b/w, notes col
  10. Lecture 11/11/2011: slides, notes b/w, notes col
  11. Lecture 24/11/2011: slides, notes b/w, notes col
  12. Lecture 30/11/2011: slides, notes b/w, notes col
  13. Lecture 01/12/2011: slides, notes b/w, notes col
  14. Lecture 02/12/2011: slides, notes b/w, notes col
  15. Lecture 07/12/2011: slides, notes b/w, notes col
  16. Lecture 09/12/2011: slides, notes b/w, notes col
  17. Lecture 14/12/2011: slides, notes b/w, notes col
  18. Lecture 15/12/2011: slides, notes b/w, notes col
  19. Lecture 04/01/2012: slides, notes b/w, notes col
  20. Lecture 05/01/2012: slides, notes b/w, notes col
  21. Lecture 06/01/2012: slides, notes b/w, notes col
  22. Lecture 18/01/2012: slides, notes b/w, notes col
  23. Lecture 19/01/2012: slides, notes b/w, notes col
  24. Lecture 26/01/2012: slides, notes b/w, notes col
  25. Lecture 27/01/2012: slides, notes b/w, notes col
  26. Lecture 08/02/2012: slides, notes b/w, notes col
  27. Lecture 09/02/2012: slides, notes b/w, notes col
  28. Lecture 15/02/2012: slides, notes b/w, notes col
  29. Lecture 16/02/2012: slides, notes b/w, notes col
  30. Lecture 17/02/2012: slides, notes b/w, notes col
  31.  

Download the complete set of slides here.

Exercise Sessions

  • Session 1 (2011/10/21): [slides]
  • Session 2 (2011/10/28): [slides], [b/w], [col], [ArchimedesCube]
  • Session 3 (2011/11/01): [slides], [synopsis lp files]
  • Session 4 (2011/11/09): [e-chalk col]
  • Session 5 (2011/11/16): [e-chalk b/w] [e-chalk col] [testset.png]
    Remark: There is a mistake on page 3 in the CARRY^(0) matrix for problems with phase 1. p^T does not have 0s everywhere but some -1s instead.
  • Session 6 (2011/11/18): [e-chalk col] [e-chalk b/w]
  • Session 7 (2011/12/08): [slides] [e-chalk b/w] [e-chalk-col]
  • Session 8 (2011/12/16): [e-chalk b/w] [e-chalk col]
  • Session 9 (2012/01/11): [slides] [col] [b/w]
  • Session 10 (2012/01/13): [col] [b/w] Please check out this link (sec 3) for a correction of some indices within the running time proof for the Euclidean algorithm.  
  • Session 11 (2012/01/20): [slides] (update Jan 25)

    • slide 6: in line 5 the arc is only forward for a from L
    • slide 8/9: definition of reduced cost was wrong
    • slide 12: added remark that this gives a strongly feasible spanning tree (compare Session 12)
    • slide 15: Changed the update of b(v)/b(w) to b'(v)/b'(w) because we only change the remaining demand temporarily during the procedure but not permanently.

  • Session 12 (2012/01/25): [slides]  

    • side 8: updates of demands as b'(v) and b'(w), we do not change the demands, we only keep track of remaining demand to fulfill
    • slide 10: added with specific information about preventing cycling
    • I asked Steffen to give examples in the tutorial on complementary slackness and slide 11 (update of node potentials).

  • Session 13: (2012/02/02): [col] [b/w] Fun with randomized algorithms :-)
  • Session 14: (2012/02/10): [slides] [col] [b/w]  
  • Session 15: (2012/02/17): [competition slides]

Homework & Programming tasks

  1. exercise 1 (due-date: Oct 27)[pdf]
  2. exercise 2 (due-date: Nov 2) [pdf]
  3. exercise 3 (due-date: Nov 10 at 1600) [pdf]
  4. exercise 4 (due-date: Nov 17) [pdf]
  5. exercise 5 (due-date: Nov 24) [pdf]
  6. exercise 6 (due-date: Dec 1) [pdf]
  7. exercise 7 (due-date: Dec 8) [pdf]
  8. exercise 8 (due-date: Dec 15) [pdf] (exercise 47: You can assume that G is connected and that the edge cost are non-negative.)
  9. exercise 9 (due-date: Jan 5) [pdf] (Remark: contains some funny XMas-exercise)
  10. exercise 10 (due-date: Jan 12) [pdf] (Updated 09.01.)
  11. exercise 11 (due-date: Jan 19) [pdf]  
  12. exercise 12 (due-date: Jan 26) [pdf]  (Ex. 76: by shortest path we mean cheapest path)
  13. exercise 13 (due-date: Feb 2) [pdf]  
  14. exercise 14 (due-date: Feb 9) [pdf] (last sheet)
  15. exercise 15 (without due-date) [pdf]

1. Programming exercise (due-date: Dec 11 2011))

    [pdf]

    [LPReader.java]

    [more_lps.zip]

    [netlib.zip]

2. Programming exercise (due-date: Feb 13 2012)

    [pdf]

    [Website]

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.