Combinatorial Optimization 1 (MAT.321/MAT.322)

Winter Term 2020/21

Bettina Klinz

Scheduled dates

Office hours

Contents of the course

Literature

On-line materials

Exercise sheets

Exams

Under construction ....

Scheduled dates

Tag	Zeit	Raum	Periode
Monday	10:15-12:00	SR AE06	October 4, 2021 - January , 2022
Tuesday	10:15-12:00	SR AE06	October 5, 2021 - January 28, 2020
Thursday	16:15-18:00	SR AE02	October 7, 2021 - January 29, 2020

The Monday and Tuesday slots will be devoted to the lecture part.
About every second Thursday will be devoted to the practical. The remaining Thursday slots will be used for the lecture part. Deviations from this general rule of thumb will be announced in the lecture.

Office Hours

If you happen to have questions, feel free to talk to me after the course or send me an e-mail to klinz@opt.math.tu-graz.ac.at. I'm offering virtual consultation hours via Webex or BBB if needed upon prior appointment.

Contents and Goal of the Course

The course will provide a solid introduction into the area of combinatorial optimization. The main focus will be on polynomially solvable combinatorial optimization problems (NP-hard ones are the main focus of the master course Combinatorial Optimization 2).
Note that starting from Winter Term 2014/15 the lecture part comprises 4 hours per week instead of 3 as due to a change in the mathematical programming course (Optimization 1) some material had to be moved to the Combinatorial Optimization 1 course .

I plan to cover the following topics:

Introductory examples of combinatorial optimization; motivation
Short and informal introduction into the notions from complexity theory needed in the course
Minimum spanning tree problems and related problems
Matroids and the greedy algorithm
Optimal arborescences and branchings
Shortest path problems
Maximum flow problems
Minimum cost flow problems
Matching problems
Short introduction into key concepts in integer optimization (integer hull of a polyhedron, total unimodularity, total dual integrality, and cutting planes if time permits)

Literature

The course is not based on a text book and there are no class notes available. Please take your own notes.
In the following some recommendable books are listed.

Text books and monographs

The following four books provide a good overview about the area of combinatorial optimization.

W.J. Cook, W.H. Cunningham, W.H. Pulleyblank, A. Schrijver, Combinatorial Optimization,
Wiley-Interscience, John Wiley & Sons, New York, 1998, 355 pages, ISBN 0-471-55894-X.
(Easily readable, but yet modern text book. Covers less topics than the book by Korte and Vygen.)

B. Korte, J. Vygen, Combinatorial Optimization,
Springer Verlag, Berlin, Heidelberg, New York, 2nd edition, 2002, 530 pages, ISBN 3-540-43154-3.
Very extensive book. For the German version an e-book version is available within the TU Graz network.

G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization,
Wiley-Interscience, John Wiley & Sons, New York, 1988, 763 pages, ISBN 0-471-35943-2.
(Parts of the book are outdated. The book provides a very comprehensive treatment of integer programming well beyond the scope of this course.)

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency,
Springer, Berlin, Heidelberg, New York, 2003, 3 volumes (Volume A: 648 pages, Volume B: 570 pages, Volume C: 664 pages), ISBN: 3-540-44389-4. (Very comprehensive monograph on combinatorial optimization; special focus on polyhedral results and efficient algorithms, over 400 references, almost 2000 pages!)

R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications,
Prentice Hall, Englewood-Cliffs, New Jersey, 1993, 864 pages, ISBN 0-13-617549-X.
(This book provides an extensive and very recommendable treatment of the area of network flow problems (including also topics like spanning trees and shortest paths), a subarea of combinatorial optimization.

The two books listed below are already quite old and not up to date in all aspects, however they are classics that are recommendable in their own right.

E.L. Lawler, Combinatorial Optimization: Networks and Matroids,
Dover Publications, 2001, 374 pages, ISBN 0-486-41453-1.
(Republication of the original edition that was published by Holt, Rhinehart amd Winston, New York in 1976)

C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity,
Dover Publications, Inc, 1988, 496 pages, ISBN 0-486-40258-4.
(Corrected, unabridged republication of the original edition that was published in 1982 by Prentice Hall, Englewood Cliffs, New Jersey
and has been out of print for several years.)

Bibliographies

The two following annotated bibliographies contain many further literature references for combinatorial optimization (up to at most 1997 due to their publication date):

M.O'hEigeartaigh, J.K. Lenstra, A.H.G. Rinnooy Kan (eds.), Combinatorial Optimization: Annotated Bibliographies,
Wiley, New York, 1985.

M. Dell'Amico, F. Maffioli, S. Martello (eds), Annotated Bibliographies in Combinatorial Optimization,
Wiley-Interscience, John Wiley & Sons, New York, 1997, 495 pages, ISBN 0-471-96574-X.
(covers roughly the period 1985-1997).

On-Line Materials

Link list "Combinatorial optimization" (under construction).

Some further links in an wider context can be found in my mathematical programming link list Linkliste zur mathematischen Optimierung (under construction too and currently not up to date).

Practical

General comments

There will be exercise sheets which will be discussed in the practical roughly every second week on Thursdays. Students should try to solve the exercises on their own. The exercises should help to obtain a better understanding of the material taught in the lecture part.

Not all exercises are intended to be covered in class. I added a number of additional exercise to point out connections to topics related to those treated in class and to encourage the students to extend their level of understanding of combinatorial optimization and to get acquainted with problem solving on a level adequate for an advanced bachelor course.

The degree of difficulty of the problems varies. Some are very basic, others are of average difficulty and some are actually quite challenging at this level.

If you happen to have questions to exercises not treated in class, do not hesitate to ask me for help/guidance.

Exercise Sheets

Will be made available.

Exam/Grading information

Grading of the Lecture

There will be an oral exam for the lecture. (Special arrangements possible for those who do not take part in this year's practical.)
I will not register the oral exams in TUG-Online in advance. Please make your own appointment with me (best at least a few days before you want to get examined).

When preparing for the exam, aim at understanding the material presented in the lecture. It is not sufficient to learn algorithms and proofs by heart.

Grading of the Practical

The final grade will be based on the following parts:

(a) Two exams (one mid term and one near the end of the term): up to 32 points
(b) Presenting solutions to exercise problems in the practical: up to 8 points
(c) Assignment (implementation of an algorithm or preparing a summary for a paper): up to 5 points (one extra point for exceptional work)
(d) Up to 2 extra credit points for special contributions in exceptional cases

Details for (a)

There will be two exams (you need to take part in both).

Exam 1: December 12, 2019, Lecture hall BE01, Steyrergasse 30, ground floor, 18:00

Topics covered by Exam 1: Sections 0-6 (i.e., all the material treated in class including max flow).

Exam 2: February 5, 2020, Lecture hall BE01, Steyrergasse 30, ground floor, starting time 16:00

Topics covered by Exam 2: Focus on topics not yet covered in Exam 1

For those who happen to miss one of the exams or do not end up enough points for a pass, there will be offered a single chance for a third exam (each student can choose whether he she/wants to repeat the first exam or the second exam). This extra exam will take place at the start of the next term (the date will be arranged upon mutual consent).

Details for (b)

There will be exercise sheets which will appear gradually as the semester progresses. Each announcement of a new sheet will be accompanied by a message which classifies the problem into two classes: Problems that will be handled in class and additional problems which have been added to provide you with additional material to assist your learning process and/or to help you widen and extend your knowledge beyond what is covered in the lecture.

At the beginning of each practical the students are asked to mark the problems they have prepared for with a cross. For each problem handled in class I will select one student among those who have marked the problem to present the solution on the blackboard.
It is not sufficient to have someone else solve a problem and write the solution on the blackboard without being able to explain the solution. Partial solutions will get some credit, wrong answers will get 0 points (no negative points). This should encourage students also to present solutions they are not sure about.

Details for (c)

The students can choose between two types of assignments: Implementation assignments and Paper reading assignments. Let me know your choice so that I can assihn you a project of your chosen type.

Implementation assignments/projects: You will get assigned by me one of the algorithms taught in the lecture (do not make your own choice!) and your task is to implement the algorithm. If you happen to wish another programming language than C/C++, please talk to me first.

Paper reading assignments/projects: This type of assignment is thought for all those who wish to avoid implementation work. You will get assigned by me a paper about a combinorial optimization topic (not covered in the lecture but related) and your task is to read the assigned paper and to write up a summary.

Minimal requirements for passing:

At least 14 points in total at the two exams.
At least two successful presentations of exercise problems at the blackboard.
At least 22 points in total.

Grading key:

0 <= P < 22	Grade 5 (Nicht genügend)
22 <= P <= 28	Grade 4 (Genügend)
28 < P <= 35	Grade 3 (Befriedigend)
35 < P < =41	Grade 2 (Gut)
41 < P	Grade 1 (Sehr gut)

where P denotes the total number of points.

Last update: October 3, 2021
Bettina Klinz (klinz@opt.math.tu-graz.ac.at)