Discrete Optimization
TDA206 / DIT370 • Period 3 • 2018
The exam has been graded, and you should find your grades in the system soon. The overall distribution of points for the course is shown above; students who did not submit an exam have been excluded from the figure. Exam solutions can be found here. Thanks for all your hard work!
The exam points (max. 42) will be added to the homework points to obtain the final course points (max. 60). The course grade is calculated as follows:
|
Point range |
Chalmers grade |
GU grade |
|---|---|---|
|
48-60 |
5 |
VG |
|
36-47 |
4 |
G |
|
28-35 |
3 |
|
|
0-27 |
U |
U |
Solutions for homework will be uploaded for self-study, see below.
The old exam for practicing purposes can be found below.
In order to find a date for the take-home exam, please participate in the Doodle poll. UPDATE: Since we couldn’t find consensus, we’ll have the exam on the one date which has no Chalmers-internal scheduling conflicts: Saturday, 10.3. 15:00 to Sunday, 11.3., 15:00.
By popular request, last year’s course website can be found here. We roughly follow the course structure, and you are welcome to use the material for preparation. Lecture notes for this year’s class will be uploaded regularly to reflect the actual material covered in class.
Welcome to the class! Please register in the FIRE system for homework submissions.
3(b): By “scheme of ILP primal-dual relationships” we mean the scheme we used to derive the dual (like Fig. 1 in lecture notes 2). It is easier to talk about PDM using this, not the explicit “max … s.t. ...” forms of primal and dual.
A general remark: Unless it is specified that you are supposed to execute an algorithm manually, such as 3(d), you may use CVX to solve an LP, of course. Include your code, it helps in case you had a typo and got the wrong solution. In question 2, we want to see an actual argument, not a CVX solution.
1(d)-(g): You may use whichever form of LP you like (original or standard). Standard is probably easier to work with.
Typo in 2(b): x is integer of course, not real.
For practicing purposes, no solutions will be provided yet.
The 2017 exam can be found here, and a version with solutions can be found here. Consider solving the exam first using the PDF without solutions, to counteract the “Oh yeah, that’s how I would’ve done it”-effect.
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.
Lectures will be Mondays and Wednesdays at 10:00-11:45 in SB-H3 (V-huset).
The schedule can be found on TimeEdit. You can also import it to your devices in iCal format.
John Wiedenhoeft, john.wiedenhoeft@chalmers.se, Homepage, room EDIT 6449, consultations: Thursdays 14:00-15:00
Assistants will take turns offering consultations on Tuesdays 10:00-11:00, and by arrangement, in room EDIT 5354.
Elisabet Lobo Vesga, elilob@chalmers.se, Homepage
Simon Robillard, simon.robillard@chalmers.se, Homepage
Marta Bravo (exchange student), martabr@student.chalmers.se
Victor Ebberstein (MPALG), vicebb@student.chalmers.se
Emil Jansson (TKITE), jaemil@student.chalmers.se
Renjith Sebastian (MPALG), renjith@student.chalmers.se
Ze Zhang (MPSYS), zhze@student.chalmers.se
See also the syllabus of this course.
This course is intended to provide a basic understanding of mathematical optimization and its applications. In optimization problems, the main goal is to obtain the maximum (or minimum) value of an objective function, often under a set of additional conditions and constraints. 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 methods to tackle 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 to which class a given problem belongs
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
Elementary Linear Algebra
Algorithms
Elementary mathematical analysis/calculus
Elementary MATLAB
Furthermore, some basic knowledge of graph theory will be helpful. However, sufficient explanation for the graph-theoretic concepts will be provided when required.
The lectures and evaluation will be based on the instructor'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.
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.
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.
Grading is based on hand-in exercises (30% of the final grade) and a final take-home exam (70% of the final grade).