TDA206/DIT370, Period 3, 2012: Discrete Optimization

Instructor

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

Assistant

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

Announcements

Student representatives: Thomas Bååth Sjöblom (thobaa), Gustav Landen (lgustav), Christoffer Andersson (chrander).
Exercises 1-4, Exercises 5-7, Exercise 8, Exercises 9-11, GLPK exercises, Home exam with answers. Deadlines have expired.
Individual exam feedback and final grades will be mailed to you when the grading is finished.

Times and Places

Monday 10:00-11:45, room ML3: lecture.
Wednesday 13:15-15:00, room ML1: lecture. (TimeEdit wrongly says "exercises".)
Wednesday 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.
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 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

Lecture 1. Modelling optimization problems as LP or ILP.
Lecture 2. More linearization tricks. Simplex algorithm. Geometry of (I)LP.
Lecture 3. NP-completeness of ILP. Preflow-push algorithm for max-flow.
Lecture 4. Min-cost flow. Integrality and unimodular matrices. Briefly about heuristics.
Lecture 5. Christofides' algorithm for TSP. LP relaxation. Branch-and-bound.
Lecture 6. Branch-and-bound applied to specific problems. Cutting planes.
GLPK tutorial 1 (.rar file).
Lecture 7. Problem-specific cutting planes: Cover inequalities for Knapsack. Branch-and-cut, example: STSP. Dual LP and ILP.
Lecture 8. Lagrangian optimization and dualization.
Lecture 9. Lagrangian dualization, example: Held-Karp method for STSP. Column generation.
Lecture 10. Graph coloring and applications.
Lecture 11. Edge coloring in bipartite graphs (short lecture).

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.