Discrete Optimization
TDA206/DIT370, Period 3, 2017
We are done grading, and you should receive your final course grade soon. The figure below shows the final point distribution for the course (homework + exam). Students who have not taken the exam were excluded from the figure. The number of attainable points was 50, partial point totals for the course have been rounded up to the next integer. Since there is this obvious peak at 22 points, we decided to make 22 instead of 23 the threshold for a passing grade (3 or G).
The exam solutions can be found here.
A supplementary task to improve grades can be found here. The deadline is Monday, May 1, 2017, 16:00. Please refer any questions to Birgit.
4: We can make people work as many 8-hour shifts in a row as we want.
4: A worker starting at 20:00 works until 4:00 the next morning. The entire schedule wraps around. You may assume that it goes on forever, and that it has been going on forever (you do not need to take care of how to get this entire schedule started).
4: Each 8-hour shift starts at the beginning of a 4-hour time slot. So each 8-hour shift consists of 2 subsequent time slots.
1a: The dual should be found directly for the problem as it is given, NOT for the standard form in (b).
4: All we care about are the total number of 8-hour shifts we have to pay for. There are no constraints as to how many shifts a worker can do, for example. We are also not concerned with questions like the maximum number of workers we have to have on our payroll to be able to fill the shifts.
Read 1c very carefully!
1b: Ax >= b is correct, this is a MINimization problem. The dual of a maximization standard form is itself considered a standard form. Also note that standard form requires x >= 0.
The take-home exam is now online: Download Lycka till! If you have questions during the exam, please send an email to Birgit and John. We will be available until 18:00. We will post updates such as corrections of typos or clarifications of ambiguous phrasing on this website, so please do check back from time to time.
Exam rules: We will post rules on the exam itself. The general idea is: All submissions have to be your own work (NO GROUP WORK). You may use whatever sources of information and tools you wish, as long as you are not actively asking others for help or collaborate with someone. For example, you may use answers you find on sources like StackExchange.com to help with your solution, but you may not post exam questions there and ask others to help you. The correctness of sources is your responsibility, i.e. if you take a wrong solution from somewhere you will lose points, and cannot blame your source (except if the error is in the lecture notes or the suggested literature).
You will find old exams here, here, here, here, and here. Please note that these are from different instructors, and might have a different focus or level of difficulty.
In preparation for the exam, we will be offering the following office hours:
Thursday, 9.2., 13:15-15:00: John
Friday, 10.2., 13:15-15:00: Simon
Monday, 13.2., 10:00-11:45: Prasanth
Tuesday, 14.2., 15:15-17:00: Birgit
By arrangement (please send an email if you cannot make it to any of these).
The take-home exam will be Wednesday, March 15, 10:00 am to Thursday, March 16, 10:00 am. Details to follow on this website.
Grading is based on hand-in exercises (30% of the final grade) and a final take-home exam (70% of the final grade).
Since one week was canceled and we therefore only covered 5/6-th of the material, the final grade will be calculated by rescaling the original 60 points (18 HW + 42 exam) as follows:
We had 5 instead of 6 assignments, so each homework still counts as 3 points, and the maximum number of homework points attainable is 18*5/6=15.
The course total (homework+exam) will be 60*5/6=50 points.
This leaves 50-15=42*5/6=35 points for the exam.
Grading scales are adjusted accordingly, multiplying boundaries by 5/6 and rounding in the students’ favor; the passing grade has been lowered to 22 (instead of 23, see above):
|
Point range |
Chalmers grade |
GU grade |
|---|---|---|
|
40-50 |
5 |
VG |
|
30-39 |
4 |
G |
|
22-29 |
3 |
|
|
0-21 |
U |
U |
John Wiedenhoeft, Data- och informationsteknik, room 6449, john dot wiedenhoeft at chalmers dot se, Homepage
Birgit Grohe, Data- och informationsteknik, room 6483, grohe at chalmers dot se (contact person)
Prasanth Kolachina, Data- och informationsteknik, room 6113A, prasanth dot kolachina at cse dot gu dot se
Simon Robillard, Data- och informationsteknik, room 5453, simon dot robillard at chalmers dot se
There are three course evaluators:
Alma Otterdag, almao at student dot chalmers dot se
Axel Olivcorna, gusoliax at student dot gu dot se
Erik Thorsell, erithor at student dot chalmers dot se
Lectures will be given on Mondays and Wednesdays at 10:00 in SBH3 (V-huset).
The link to timeedit.
Lecture notes and other material will be available here. Note that the lecture plan is tentative and subject to change. If you find any typos or errors, please feel free to send an email to John. Lecture notes contain a timestamp at the bottom of every page, so you can make sure you always have the latest revision.
Week 1: Convex Optimization
Week 2: Linear Programming
Week 3: Integer Linear Programming
Week 4: Primal-Dual Method
Week 5 & 6: Branch-and-Bound, Cutting Planes and TSP
The lectures and evaluation will be based on the teacher's lecture notes, the material covered in class and the exercise sets. Therefore, you do not need to buy any book, but the lecture notes are partly based on the books below, which you can read if you are eager to know more:
Matoušek, Jiří, 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. (free download)
Calafiore, Giuseppe and Laurent El Ghaoui. Optimization Models. Cambridge University Press 2014.
See also the syllabus of this course.
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.
Update: By popular request, here is a list of possible future topics. Note that, due to time constraints, this list is very tentative and subject to change, and we will almost certainly not be able to cover everything in the remainder of this course. It should be treated as a rough guideline for students who want to get deeper into the literature, but nothing on this list is mandatory unless covered in the lectures:
Inapproximability results
Nash equilibrium
Column generation
Branch-and-bound
Cutting plane methods, Chvátal-Gomory cuts, Branch-and-cut, TSP
Lagrangian duality and relaxation, Karush-Kuhn-Tucker conditions
Gradient descent
Submodular optimization, matroid and knapsack constraints
Elementary Linear Algebra
Algorithms
Elementary mathematical analysis/calculus
Elementary MATLAB
Further knowledge of graphs will be helpful. However, sufficient explanation for the graph-theoretic concepts will be provided when required.
Each set of exercises should be submitted before the announced deadline.
We will use the MATLAB based optimization tool CVX.
Find links to download the systems here: MATLAB, CVX.
Run cvx_setup in matlabs command window to get started with the optimization tool.
Exercise set 1: deadline 2017-01-25 10:00 a.m.
Exercise set 2: deadline 2017-02-01 10:00 a.m.
Exercise set 3: deadline 2017-02-08 10:00 a.m.
Exercise set 4: deadline 2017-02-15 10:00 a.m.
Exercise set 5: deadline 2017-03-01 10:00 a.m.
All exercises are submitted individually in the FIRE SYSTEM. Deadlines are sharp. No resubmissions or late submissions will be possible.
You are allowed and encouraged to work in groups, but you must write down your solutions yourself (no verbatim copies, as far as that’s feasible). You also have to include the names of the people that you discussed with. Groups can be different each week.
A check list for your submissions:
Name and contact email in each file?
Names of your collaboration partners (if applicable)?
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 or have been given in the lecture.
The exam is in the take-home format. The take-home exam will be Wednesday, March 15, 10:00 am to Thursday, March 16, 10:00 am. Details to follow on this website.