TDA206/DIT370, Period 3, 2013: Discrete Optimization

Instructor

Peter Damaschke, EDIT 6478, ptr(at)chalmers.se

Assistant

Azam Sheikh Muhammad, EDIT 6453, azams(at)chalmers.se

Announcements

Student representatives: Joel Wilsson (wjoel), Alexander Lundgren (a_lundgren74(at)hotmail(dot)com), Birger Rydback (rydback(at)gmail(dot)com).
Exercises 1-3. Exercises 4-6. Exercise 7. GLPK exercises. Exercises 8-9. Deadlines have expired.
All GLPK-related questions should be directed to Azam, all others to Peter.
Reading assignment towards the home exam.
Home exam now with answers. Compare with yours.
When grading is finished, grades will appear in Ladok. For efficiency reasons, exam feedback and grade motivations will be sent upon request only.
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 the higher level.) 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.

Lecture Notes

Lecture 1. Modelling optimization problems as ILP.
Lecture 2. More modelling. Simplex algorithm. Complexity of LP and ILP.
Lecture 3. Preflow-push algorithm.
Lecture 4. Minimum cost flow. Unimodularity. General heuristics.
GLPK tutorial material.
Lecture 5. Christofides' algorithm. Branch-and-bound.
Lecture 6. Branch-and-bound continued. Cutting plane methods.
Lecture 7. Branch-and-cut, example: Gomory-Hu method for TSP. - Dual LP.
Lecture 8. Lagrange multipliers.
Lecture 9. Lagrange dual example: traveling salesman. - Column generation.
Lecture 10. Graph coloring.

Times and Places

Monday 10:00-11:45, room ML4: lecture.
Wednesday 10:00-11:45, room ML13: 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.

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.
Here is some material about the GLPK solver:
GLPK software package.
GLPK tutorial 1 (IBM)
GLPK tutorial 2 (IBM)
GLPK tutorial 3 (IBM)
GLPK wiki book
about algorithms used in GLPK

Grading

Grading is based on compulsory hand-in exercises and a take-home exam. (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 well explained, perhaps with minor difficulties.
4/G: mainly good solutions, but also some difficulties or gaps.
3/G: you show a basic understanding and can manage the majority of exercises, but with substantial difficulties.
U: insufficient understanding and fundamental difficulties 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.

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.

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 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. Also, you need not prove 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. If you got only a minor comment, it may be enough to clarify it directly.