Algorithms for decision support

Course goals

A student that successfully finishes the course will:

• know central concepts and algorithms from combinatorial optimization including linear and integer linear programming
• be able to model problems from applications as an (integer) linear program
• know central concepts and algorithms from online algorithms, and is able to analyse the behavior of an online algorithm
• have basic knowledge about online algorithms and competitive analysis (and further with machine learning advice)
• have knowledge of important concepts and proof techniques from algorithmic complexity, including undecidability, NP-completeness, etc.
• be able to understand and design NP-completeness proofs

Assessment
There is a project done in groups (40% of the final mark) and two exams, both an approximately half of the materials (30% each).
You must have at least a 4.5 for the project and for the average of the exams to pass the course, and at least a 5.5 for the overall average.

If the project was graded less than 4.5, and you have an average of at least 4 for the exams and the project, you can do a new project.
If the average of your exams was graded less than 4.5, and you have an average of at least 4 for the exam and the project, you can do the re-exam.
If your average was at least 4 and less than 5.5, you can do the re-exam.

Details on grading for the 2nd chance exam or project can be found on the Brightspace site of the course.

Prerequisites
Basic logic and reasoning.

Content

The purpose of this course is to teach topics that are:

• important for the working area of algorithms (in practice and theory)
• prerequisites for other courses in the COSC program
• not encountered by all students in the bachelor.

It therefore contains a broad range of topics.

In many real-life decision problems in e.g. (public) transportation, logistics, energy networks, healthcare, computer networks and education we want to select a very good solution from a large set of possible solutions.
In the course you learn how to model such problems and how to solve them by optimization algorithms. We focus on discrete models.
You shall learn about computational complexity and about meaning of exact optimization algorithms, heuristics and what-if analysis.
We study well-known algorithms from combinatorial optimization, in the scope of linear programming, online algorithms, randomized algorithms, etcetera.

Course form
Lectures, self-study, exercises, assignments.

Literature
The material of the course consists of course notes and slides. 

The following books are not mandatory but interesting for further reading:

• Laurence A. Wolsey, "Integer Programming", Wiley-Interscience publication, 1998, ISBN 0-471-28366-5.
• M.R. Garey and D.S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", W.H. Freeman and Company, New York, 1979, ISBN 0-7167-1044-7..