TDA206/DIT370, Period 3, 2016: Discrete Optimization

Instructor

Ashkan Panahi, EDIT 6476, ashkanp(at)chalmers.se

Assistants

Simon Robillard, EDIT 5453, simon.robillard (at) chalmers.se
Daniel Schoepe, EDIT 5449, schoepe (at) chalmers.se
Brigit Grohe, EDIT 6476, grohe (at) chalmers.se

Announcement

Lectures will be given on Mondays and Wednesdays at 10:00, in room AL5 (A-huset).
Use the "Fire" system to hand in you assignments. Register yourself here. The direct address is "https://xdat09.ce.chalmers.se/2016/lp3/do/".
The first hand-in assignment is uploaded. See below. Deadline: 01/29 at 23:59.
The grading details are published. See section "Grading" below.
The second hand-in assignment is released. See below. Deadline: 02/05 at 23:59.
In the fire system, the deadlines for the assignments were wrong and are corrected now.
Lecture note 5 is updated and lecture note 6 is added.
Matlab codes are added.
In the exercise section below, you can now find the name of the graders for each assignment.
The third hand-in assignment is released. See below. Deadline: 02/19 at 23:59.
A typo is found and corrected in the lecture notes: On Page15 Item No.4, some inequalities are flipped.
Lecture notes for the 7th lecture are uploaded.
Lecture notes for the 8th lecture are modified.
The exam date and instructions are released. See the exam section.
The fourth hand-in assignment is released. See below. Deadline: 02/26 at 23:59.
Lecture notes for the 10th lecture are modified. The MATLAB code for the 9th lecture is added.
The fifth hand-in assignment is released. See below. Deadline: 03/04 at 23:59.
Lecture notes for the 11th lecture are released.
Lecture notes for the 12th lecture are released.
In the notes for the 9th lecture, the numberings are corrected. The 4th exercise now points to the correct example.
In the notes for the 9th lecture, some typos are corrected (y is replaced by u at some points).
The sixth hand-in assignment is released. See below. Deadline: 03/11 at 23:59.
The exam is released. Download the exam HERE or in the examination part.
Find the exam grading details in the Grading section.
The exam is finished. Find the suggested solutions HERE

Lecture Notes

The lectures and evaluation will be based on the teacher's lecture notes. Therefore, you do not need to buy any book, but the lecture notes are based on three books, which you can read only if you are eager to know more:

Matousek, Jiri, and Bernd Gärtner. Understanding and using linear programming. Springer Science & Business Media, 2007.
Wolsey, Laurence A. Integer programming. Vol. 42. New York: Wiley, 1998.
Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

The third one is free to download from the authors’ homepage.

Lecture Sessions

Here is a tentative schedule for the sessions:

Lecture 1: Introduction and basic concepts. Monday, 01/18 at 10:00, AL5, Lecture Notes
Lecture 2: Continuous Optimization, convexity and convex optimization. Wednesday, 01/20 at 10:00, AL5, Lecture Notes, MATLAB code
Lecture 3: Linear programming, basic concepts and different forms. Monday, 01/25 at 10:00, AL5, Lecture Notes, MATLAB code (min flow)
Lecture 4: Linear programming, real-world examples. Wednesday, 01/27 at 10:00, AL5, An excerpt from Book 1, MATLAB code (ice cream!), MATLAB code (ice cream! LP)
Lecture 5: Duality in linear programming. Monday, 02/08 at 10:00, AL5,Lecture Notes, MATLAB code
Lecture 6: Complementary slackness conditions, duality in the minimum cost network flow problem. Wednesday, 02/10 at 10:00, AL5, Lecture Notes
Lecture 7: Integer linear programming, modeling and examples. Monday, 02/15 at 10:00, AL5, An excerpt from Book 2,
Lecture 8: LP relaxation, integrality gap and examples. Wednesday, 02/17 at 10:00, AL5, Lecture Notes
Lecture 9: The primal-dual algorithm. Monday, 02/22 at 10:00, AL5, Lecture Notes, MATLAB code
Lecture 10: Beyond LP relaxation: a brief introduction to the branch-and-bound, and the cutting plane methods. Wednesday, 02/24 at 10:00, AL5, Lecture Notes
Lecture 11: Beyond linear programming: convex optimization and Lagrangian duality. Monday, 02/29 at 10:00, AL5, Lecture Notes
Lecture 12: Local search methods in non-linear programming. Wednesday, 03/02 at 10:00, AL5, Lecture Notes
Lecture 13: Constrained Optimization. The simplex and the interior point Methods. Monday, 03/07 at 10:00, AL5,

Book a consultation time by email when you need special help.

Brief Course Description and Goals

This course is intended to provide a basic understanding about mathematical optimization and its applications. In optimization problems, the main goal is to obtain the maximum (or minimum) amount of an objective value by a proper selection of a number of individual variables. This goal is desirable in a large variety of applications, but may be difficult to achieve. In this course, you learn how to use mathematical disciplines to treat optimization problems. Examples from different application domains will be presented. In particular, optimization problems with discrete-valued parameters are discussed.

After the course you should be able to:

identify optimization problems in various application domains,
formulate them in exact mathematical models that capture the essentials of the real problems but are still manageable by computational methods,
assess which problem class a given problem belongs to,
apply linear programming, related generic methods and additional heuristics to computational problems,
explain the geometry of linear programming,
dualize optimization problems and use the dual forms to obtain bounds,
work with the scientific literature in the field.

Prerequisites

Elementary Linear algebra, algorithms, elementary mathematical analysis, elementary MATLAB. Further knowledge of graphs will be helpful. However, sufficient explanation for the graph-theoretic concepts will be provided when required.

Grading

Grading is based on hand-in exercises and a final take-home exam :

Each set of exercises is graded as 0,1, 2 or 3:
- Grade 0: Not submitted or very poorly solved.
- Grade 1: The solution is incorrect or lacks sufficient explanation.
- Grade 2: The solution is correct, but has some flaws.
- Grade 3: The solution is correct and sound, with possible minor mistakes.
In toatl, there are 6 sets of exercises with 18 points (3 points each).
The final take-home exam worths 18 points in total.
There are 6 questions in the final exam. Each question is worth 3 points.
Submitting your assignments and the final exam, you may maximally earn 36 points (18+18). Your reprted grade can be calculated as follows:
- U(Fail): You earn less than (and not equal to) 18 points.
- G,3: You earn more than (or equal to) 18 points, but less than (and not equal to) 24 points.
- G,4: You earn more than (or equal to) 24 points, but less than (and not equal to) 30 points.
- VG,5: You earn more than (or equal to) 30 points.

Exercises

Each set of exercises should be submitted before the announced deadline. Notice that there is NO possible resubmission after the deadline .

Assignment 1: Download (Simon and Daniel). Deadline: Friday 01/29 at 23:59.
Assignment 2: Download (Simon and Birgit). Deadline: Friday 02/05 at 23:59.
Assignment 3: Download (Simon and Daniel). Deadline: Friday 02/19 at 23:59.
Assignment 4: Download (Simon and Birgit). Deadline: Friday 02/26 at 23:59.
Assignment 5: Download. Deadline: Friday 03/04 at 23:59.
Assignment 6: Download. Deadline: Friday 03/11 at 23:59.

Exercise Submission

Solutions to the hand-in exercises must be submitted individually (not in groups!). Include your name, personal number, and email address in your submission and all attachments (We may want to print them). We use the "Fire" system to receive your assignments. Register yourself here. The direct address is "https://xdat09.ce.chalmers.se/2016/lp3/do/".

A check list for your submissions:

Name and contact email on the actual submission?
Have you answered exactly the given questions and come to conclusions?
Are all answers and claims motivated?
Are all steps of your reasoning logically strict?
Avoid unnecessary additional writing and digressions. Do not include proofs of facts that are already known.

Final Examination

Download the exam HERE. The exam solution HERE.

The exam is in the take-home format. The question sheet will be released at 9:00 am, on Thursday, March 17 on the course homepage. The answers must be written/printed on paper and personally handed to me no later than 16:00 on Friday March 18. I will be sitting in my office, room 6476 during the normal working hours.

As there is no scheduled re-exam, you can improve your grade by an individual extra assignment that addresses weak points. You can express interest before 15 April, and then the given assignment must be finished before the end of period 4. Note that this does not apply to GU students, according to GU regulations.

General Rules and Policies

Read them carefully and take them very seriously.

Exercise deadlines are strict. Delays must be well-motivated before the deadlines. Unannounced late submissions will not be considered.
It is allowed, even encouraged, to discuss the exercises during the course. Also, do not hesitate to ask if you have difficulties with the exercises, or if something is unclear.
However, you must write your final solutions on your own, using your own words, and expressing them in the way you understood them yourself.
Submitting others' work in your own name is cheating! It can lead to severe consequences, in very bad cases even suspension from studies.
Specifically, it is prohibited to copy (with or without modifications) from each other, from books, articles, web pages, etc., and to submit solutions that you got from other persons, unless you explicitly acknowledge the sources and add your own explanations.
You are also responsible for not giving others the opportunity to copy from your work. (We will not investigate who copied from whom.)
In the take-home exam you must work completely on your own and direct questions to the teachers only.

Seeking Help

It may happen that you have read and understood the material but still cannot manage an exercise. This is not necessarily a bad sign. Problem solving requires own thinking, trying different ways, detours, and so on. We are happy to help, but make a serious effort first, and specify your difficulties.

A good question is:
"I have tried approach X, but I got stuck at this point Y, because of Z. Can you give further advice?"

Bad questions are:
"Can you give me a hint where to start?"
"This is my idea - am I on the right track?"
"Where can I read more about the exercise?"