This is the website for the Practicals (also known as exercise sessions or recitation sections) of the lecture "Optimization methods" in summer 2015, which I will be attending -- and hopefully you as well! The exercise session starts at 10:40 in S6 (Malostranské náměstí, 2nd floor). For Czech students: Moje české cvičení má stránku tady.

Other practicals (in Czech) are led by my colleagues Radek Hušek and Tomáš Masařík. The lecture is taught by professor Loebl.

Study materials

• Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner). An introductory book to Linear Programming for computer scientists which covers a large part of the lecture. Very accessible and readable. Contains applications, but no exercises.
• Linear programming, A Concise Introduction (Thomas S. Ferguson). A writeup of a lecture with a similar linear programming content, but missing other combinatorial optimization topics.
• Combinatorial Optimization: Polyhedra and Efficiency (Alexander Schrijver). A series of three textbooks containing almost everything one needs to know from combinatorial optimization. A bit dense in some places, but it is readable.
• Introduction to Discrete Geometry and Lectures on Discrete Geometry (Jiří Matoušek). The first link are lecture notes from a discrete geometry class, available for borrowing at the Faculty of Math and Physics library. The second book is a normal book on the same subject. You do not need to read the whole book; the essential parts are the lectures on convexity and on convex polytopes.

Lesson plan

• Class 1 (no revision): What can LP be used for, refreshing linear algebra, flows and some graph theory. Basic LP formulation.
• Class 2 (no revision): LP and IP formulations.
• Class 3 (revision!): convexity, affinity.
• Class 4 (no revision): polytopes, faces and vertices.
• March 14: The first homework is out! Read the instructions,, go through the tutorial, solve the tasks, send me an email. Deadline: 18. 4. 2015 08:00.
• Class 5 (revision!): The simplex algorithm.
• Class 6 (revision!): Simplex algorithm again, plus some more polytope geometry. I was away this week, prof. Loebl kindly substituted.
• 31.3.: The first exam, covering Classes 1-6.
• Class 7 (no revision): Duality.
• Class 8 (revision!): Total unimodularity.
• Class 9 (no revision): Complementary slackness.
• Class 10: Plan: Primal-dual algorithms.
• 5.5.:The second exam, covering Classes 1-10.
• May 10: The second homework is out! Read the instructions, solve the tasks, send me an email. Deadline 11. 6. 2015, 08:00. I advise you to solve it early, so you can sign up for the exam early with plenty of time.
• Class 11: Preparing for an exam. Good luck!
• Class 12 on May 19 is cancelled.

Consultations

If something from the practical session is not clear to you, if you keep struggling with some definition or exercise, if you just want a chat with your TA: schedule a consultation with me!

As an experiment, I have set up fixed consultation hours below; if you want to attend a consultation, just fill in your nickname into one of the slots. The consultations are hour-long with a limit of maximum 3 students per hour. You can choose any timeslot you want. If we run out of slots, I will create some more (plus there will be more slots in the coming weeks).

If you want an English consultation (which is likely if you are attending my English practical), please fill in (EN) after your nickname. I'd be more than happy to do the consultation in English, it's just to let the Czech students know. Thanks!

If you select a slot, we will meet at the designated time in front of the PhD students office S320 on the 3rd floor of the Malostranske namesti builiding. The office is just next to S3.

Sign up here! You can see the (read-only) data below:

Points

Pass conditions

To get a pass from the practical, you need at least 60 points. You can get points via the following:

• Presenting a solution of an exercise: ~2 points per exercise.
• 5-6-times per semester: a revision for 2 points each.
• Two exams: 25 points each.
• Two sets of practical homework: 25 points each.

A revision is a way to refresh the material from the last two weeks with a mini-test containing a single exercise. It will take place roughly 5-6 times per semester, always in the first 10 minutes of the practical. Revisions are completely voluntary and are announced a week beforehand on the website.

An exam is the standard 90-minute test, containing cca 5 tasks per 5 points each. One will happen in the middle of the semester and one at the end. It will be announced 14 days in advance. The exams are voluntary as well, but we strongly recommend taking them. If you cannot attend the exam, let me know beforehand as soon as possible.

The homework sets will be practical and they will involve programming. Usually, the task will be to model a problem using linear programming and write a program/script that solves the model using an LP solver and prints the result. You will always have at least a month to finish the homework.

Notice that there are many ways to reach 60 points; choose the path that suites you the best.

We will post the current point status on the web. You can choose a nickname for your results -- do so at the first practical or via email.