TDA206/DIT370, Period 3, 2012: Discrete Optimization
Instructor
Assistant
- Azam Sheikh Muhammad, EDIT 6453, azams(at)chalmers.se
Announcements
- Course start: Monday, 16 January, 10:00, room ML3.
- On Wedneday, 18 January, the room is ED (rather than ML1).
- Due to participation in an important conference there might be changes
in the schedule in course week 2. In that case they will be announced in
good time.
- No class on Wednesday, 8 February, due to CHARM days.
Times and Places
Monday 10:00-11:45, room ML3: lecture.
Wednesday 13:15-15:00, room ML1: lecture.
(TimeEdit wrongly says "exercises".)
Thursday 15:15-17:00, room ML1: scheduled time for questions, exercise help,
and other matters.
Book a time by email when you need a consultation outside the schedule.
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.
Course material
- Own lecture notes.
- Recommended additional reading: Laurence A. Wolsey, Integer
Programming, Wiley 1998, ISBN 0-471-28366-5. The book should be available
at Cremona.
- Perhaps additional materials from other books and scientific articles.
Grading
Grading is based on compulsory hand-in exercises and a take-home
exam. (Details on how the exam works will be announced.)
We do not use a point system but we record the exercise comments and apply the
following grading criteria: 5/VG means that your solutions are on the whole correct and well explained, perhaps with minor difficulties; 3/G means that
you show a basic understanding and have an idea how to approach the exercises, but with substantial difficulties; and 4/G is between these two. You may ask
at any time during the course what your expected grade would be, based on your
performance shown so far.
There is no formal re-exam, but it is possible to improve your grade later by
follow-up assignments. (But, of course, this is not only a formality, you
must really achieve an improvement that justifies the higher grade.) You can
express your interest before April, and the assignment should be finished
before the end of study period 4.
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.
Lecture Notes
- They will be added one by one during the course.
Exercises
- 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 number. Please send only plain text or PDF
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 the week 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 really answered 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. In particular, you need
not prove facts that are already known.
- If you get 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 everything.) It may be appropriate to send an
entirely reworked solution, or it may be enough to clarify an open question -
you can decide by yourself, based on the comments.