Advanced Linear Programming 2012

Lecturers: Leen Stougie, Vrije Universiteit and CWI Amsterdam.
E-mail: stougie@cwi.nl

Marjan van den Akker, Utrecht University
E-mail: marjan@cs.uu.nl

Course materials

The course is covered by the book `Introduction to Linear Optimization', Bertsimas and Tsitsiklis, Athena Scientific 1997, ISBN 1-886529-19-1. According to some students the book cannot be ordered through ball.com or similar companies. It can be ordered directly from the publisher Dynamic Ideas through website: http://www.dynamic-ideas.com/Books/188652919/LinOpt.html

For a more basic course on linear programming I refer to books titled Introduction to Operations Research , e.g. by Hillier and Lieberman, or by Taha. Another very good book on linear programming is written by Chvatal. Everything you ever wish to know about the Theory of Linear and Integer Programming is found in the more advanced book with that title by Lex Schrijver.

Examination

The examination consists of a written exam on Monday May 14, 2012, in Utrecht (exact time and place to be announced). Consult for upcoming information the LNMB web-site . There will be a re-exam on Monday June 18, 2012, in Utrecht (exact time and place to be announced). There will not be a third possibility for passing this course in the academic year 2011-2012! Thus, students who only attend the re-exam have only one possibility to pass this academic year!

During the examination no books or any other material is allowed

Below you find examples of exams in the past. There will be some shift towards exercises that are not so much application of algorithms to instances of problems (at least one such an exercise will remain). For example you may expect one or two of the exercises that were given during the course. The first exercise of the exam will remain the same: the formulation of the standard Farkas Lemma. test1 and the exam of May 18, 2009 with the answers. The exam of May 10, 2010. Unfortunately, we had no time to make the answers, but some exercises were exercises of the course and you can find the answers in the solutions file.

Course week by week (updated every week) with workouts of exercises at the bottom of the page. Thus what you find now is only a plan.

• Reading:
  Chapter 1: Entirely
  Chapter 2: We skip Sections 2.7 and 2.8.
  
• Exercises:
  1.5, 1.15, 2.6, 2.15. The exercises can be found in the scanned copy of Chapters 1 and 2 of the book (see above)
• The lecture notes I made for myself for teaching can be found here in .pdf format.

• Reading:
  Chapter 3: We skip Sections 3.5 and 3.6.
• Exercises:
  3.7, 3.18. Who wishes may try 3.27. The exercises can be found in the scanned copy of Chapters 2 and 3 of the book (see above)
• The lecture notes I made for myself for teaching can be found here in .pdf format.

• Reading:
  Chapter 4: 4.1-4.7; We skip Sections 4.4 and 4.5
  
• Exercises:
  
4.26, 4.31, 4.35
• The lecture notes I made for myself for teaching can be found here in .pdf format.

• Reading:
  Chapter 4: 4.8--4.10
  Chapter 5: We skip Section 5.5
  
• Exercises:
  
4.39, 4.40, 4.44b (in view of the general Minkowski Theorem in these notes; you may try to prove Minkowski's Theorem through 4.46 and 4.47), 5.9
• The lecture notes I made for myself for teaching can be found here in .pdf format.

• Reading:
  Chapter 7: 7.1-7.4
  
• Exercises:
  
• 7.2, 7.14, 7.17
• The lecture notes I made for myself for teaching can be found here in .pdf format. For examples, I made a powerpoint presentation which you find here in .pdf format.

• Reading:
  Chapter 7: 7.5-7.8. Read for yourselves 7.9 and 7.10
  
• Exercises:
  
7.19, 7.20, 7.28, 7.29, 7.32 and you may try 7.30.
• The lecture notes I made for myself for teaching can be found here in .pdf format. For examples, I made a powerpoint presentation which you find here in .pdf format.

• Reading:
  Chapter 6: 6.1-6.4
  
• Exercises:
  
6.1, 6.8

• Reading:
  Chapter 8: 8.1-8.3
  
• Exercises:
  
8.2

• Reading:
  Chapter 8: 8.3-8.5
  Chapter 10: 10.1 start
• Exercises:
  
10.1 and the extra exercise

• Reading:
  Chapter 10: 10.1-10.3 10.4 and 10.11
• Exercises:
  
10.4, 10.11

• Reading:
  Chapter 11: 11.1,11.2
• Exercises:
  
11.1 a)- d) and 11.4

• Reading:
  Chapter 11: 11.4

• The answers to most of the exercises of the Weeks 1-6 can be found here in .pdf format. Since so far none of the students gave a try on Exercise 6.8, there is no answer for this exercise. At least some of the students should give the exercises a serious try before the teacher will formulate a correct answer based on the hand-ins from the students. The same holds for Exercise 8.5 of week 8.
  Please, send me any corrections if you find errors (see e-mail address at the top of the page).

We appreciate it very much if at the end of the course you would complete the Evaluation form and return it to Greta Oliemeulen-Loew (for the address see http://www.mastermath.nl).