Advanced Linear Programming 2018

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

Marjan van den Akker, Utrecht University
E-mail: J.M.vandenAkker@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. Since the past has taught that many students do not have the book yet at the start of the course, I make a copy available of the first five chapters.

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 and a re-exam, both to be announced. The exam is scheduled Monday 4 June 2018, 13:30-16:30, Edu Beta, Uithof, Utrecht, and the retake is scheduled Monday 25 June 2018, 13:30-16:30, location to be announced. You may check for updates on these data on the website of Mastermath https://elo.mastermath.nl/. There will not be a third possibility for passing this course in the academic year 2017-2018! Neither any individual oral exam! Thus, students who only attend the retake have only one possibility to pass this academic year and take a deliberate risk, which is fully their own responsibility!

During the examination no books or any other material is allowed

Below you find examples of exams in the past. The first exercise of the exam is always the same: the formulation of the standard Farkas Lemma. As an example of an exam find the exam of May 27, 2013. with answers.

Course week by week (updated every week) with workouts of exercises at the bottom of the page.

• Reading:
  Chapter 1: Entirely
  Chapter 2: We skip Sections 2.7 and 2.8.
  
• Exercises:
  1.5, 1.15, 2.6, 2.15.
• The lecture notes I made for myself for teaching.

• Reading:
  Chapter 3: We skip Sections 3.4, 3.5 and 3.6. Although 3.4 is interesting for who has never seen why the anti-cycling rule works.
  Chapter 4: 4.1-4.3
  
• Exercises:
  3.7, 3.18. Who wishes may try 3.27.
• The lecture notes I made for myself for teaching.

• Reading:
  Chapter 4: We skip section 4.4, 4.5 and 4.10
  
• Exercises:
  
4.26, 4.31, 4.35, 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).
• The lecture notes I made for myself for teaching.

• Reading:
  Chapter 7: 7.1-7.4
  
• Exercises:
  
• 7.2, 7.14, 7.17
• The lecture notes I made for myself for teaching. For examples, I made a powerpoint presentation which you find here in .ppt 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, and you may try 7.30.
• The lecture notes I made for myself for teaching. For examples, I made a powerpoint presentation which you find here in .ppt format.

• Reading:
  Chapter 8.
  
• Exercises:
  
8.1,8.2,8.9
• The lecture notes I made for myself for teaching.

From here on Marjan van den Akker takes over. For the week-by-week continuation of the course, you are invited to go to Marjan's website.

• Answers to exercises can be found here in pdf format.
  Please, send me any corrections if you find errors (see e-mail address at the top of the page), or answers to problems that are missing. I update the file if new or corrected answers become available. So check every now and then.

We appreciate it very much if at the end of the course you would complete the evaluation form and return it to MasterMath (for the form and the address see https://elo.mastermath.nl/).