TDA206/DIT370, Period 3, 2015: Discrete Optimization
Instructor
Assistants
- Simon Robillard, simon.robillard(at)chalmers.se
- Daniel Schoepe, schoepe(at)chalmers.se
Announcements
Lecture Notes
- Lecture 1.
Mathematical Optimization. LP and ILP. Convexity. First problem examples.
- Lecture 2.
More examples of LP and ILP formulations and "linearization tricks":
Fitting a line (regression). Network flows. Covering and packing. Job
assignment problem.
- Lecture 3.
Disjunctive constraints. Modelling initial costs. Traveling salesman as
ILP. Boolean expressions and NP-completeness of ILP.
- Lecture 4.
Simplex algorithm for LP and its complexity.
- Lecture 5.
LP relaxation. Totally unimodular matrices.
- Lecture 6.
Duality of covering and packing. LP strong duality. Duality of max-flow
and min-cut. Matrix games.
- Lecture 7.
Branch-and-bound with example: knapsack.
- Lecture 8.
Cutting plane methods. Gomory-Chvatal inequalities. Cutting planes for
the traveling salesman. Branch-and-cut.
- Lecture 9.
Column generation methods with example: cutting stock problem. Lagrange
multipliers. Lagrange method for continuous constrained problems.
- Lecture 10.
Lagrange continued: Treating equality and inequality constraints.
Lagrangian dual: weak duality and concavity. LP dual revisited.
- Lecture 11.
A Lagrangian dual of the traveling salesman (Held-Karp method). Graph
coloring problem with some applications (intro).
- Lecture 12.
Coloring interval graphs and cocomparability graphs. Edge coloring of
bipartite graphs.
Times and Places
Monday 10:00-11:45, room VO11: lecture.
Wednesday 10:00-11:45, room VO12: lecture.
Book a consultation time by email when you need special help.
Brief Course Description and Goals
You learn in this course specific methods to model and solve problems where
some objective function shall be maximized or minimized under side
constraints, especially for discrete problems, i.e., such with countable
objects and integer variables.
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
Linear algebra, algorithms, data structures. Some knowledge of graph theory
is helpful, too, however, graph concepts will be introduced when needed.
Grading
Grading is based on compulsory hand-in exercises and a take-home
exam which count equally. (Details about the exam will be announced in
good time.)
We do not use a point system and predefined thresholds, but we record the
exercise comments and apply the following grading criteria.
5/VG: Your solutions are correct and also well explained, with at most
minor errors.
4/G: Mainly good solutions, but also some errors or gaps remain.
3/G: You show a basic understanding and could manage the majority of
exercises.
U: Insufficient understanding and fundamental errors in most
exercises.
Hence not all exercises need to be "OK'd" to pass the course; but your ability
to solve them is decisive for the grade. You may ask at any time during the
course what your expected grade would be, based on your performance shown so
far.
As there is no scheduled re-exam, you can improve your grade by an individual
extra assignment that addresses weak points. (However, this is not only a
formality, you must really achieve a level that justifies a higher grade.)
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 firm. Delays must be 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.
Exercise Submission
- Solutions to the hand-in exercises must be submitted individually
(not in groups!) by email to "ptr..." The subject line should contain the
course code and exercise numbers. Please send only PDF (preferable) or
plain text attachments, no other formats. Write your name, personal
number, and email address also on the submitted attachments. (We may want
to print them.) Preferably send all solutions of an exercise set in one
document, rather than a separate mail or file for each exercise.
- 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?
- If you could not solve an exercise, point out where you got stuck.
This may help us to give further hints.
- Avoid unnecessary additional writing and digressions. Do not include proofs
of facts that are already known.
- If you got exercise feedback: Complete and improve your solutions
accordingly and resubmit as soon as possible. The earlier you resubmit, the
more chances you have. The number of attempts is not limited. There will be only one final deadline for all resubmissions at the end of the course.
Usually it is appropriate to send an entirely reworked solution. Say what
you have changed compared to the previous version. If you got only a minor
comment, it may be enough to answer directly.
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?"