Introduction to Linear and Combinatorial Optimization (ADM I)

• (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.
  

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

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

 

Download the complete set of slides here.

• 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]

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]