Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Human Computer Interaction Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Algorithms for decision support

Website:website containing additional information
Course code:INFOMADS
Credits:7.5 ECTS
Period:period 1 (week 36 through 45, i.e., 2-9-2019 through 8-11-2019; retake week 1 (bachelor) / 2 (master))
Participants:up till now 119 subscriptions
Schedule:Official schedule representation can be found in MyTimetable
Teachers:Dit is een oud rooster!
lecture          Marjan van den Akker
Alison Liu
tutorial group 1        Roel van der Broek
Ruben Meuwese
Contents: Due to illness, there is no lecture on Thursday September 5!!!

In data science we distinguish:

  • Descriptive analysis: what is the current situation?
  • Predictive analysis: what is going to happen in the future?
  • Prescriptive analysis: which decision should I make?

This course and other courses in the field of algorithms focus on prescriptive analysis .

The purpose of is to teach topics that:

  • are important for the working area of algorithms (in practice and theory)
  • are prerequisites for other courses in the COSC program
  • that are 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 simulation and/or optimization algorithms. We focus on discrete models. You learn about computational complexity and about meaning of exact optimization algorithms, heuristics and what-if analysis. For deterministic problems, we study well-known algorithms from combinatorial optimization. In particular, we study integer linear programming, since it is one of the most frequently applied techniques in practice. For stochastic problems, we study discrete-event simulation . As assignment you have to perform a simulation study of the Uithoflijn, the new tram line that will connect Utrecht CS and the Uithof.

The learning outcomes of the course are

  • Knowledge of discrete-event simulation models and combinatorial optimization models
  • Knowledge of methods for experimental research with discrete-event simulation including statistical methods
  • Insight in the complexity of combinatorial optimization problems
  • Knowledge of well-known types of combinatorial optimization algorithms
  • Ability to model problems from applications as a discrete-event simulation problem and as a combinatorial optimization problem
  • Ability to perform a scientific sound simulation study including statistical analysis
  • Ability to apply the algorithms from the course to combinatorial optimization problems
Literature:The material of the course consists of:
  • Simulation : slides, references to sections of the book by Law (copies of the most important section are available), exercises, and some solutions. There is also background material on statistics.
  • Integer linear programming : slides, lecture notes, exercises, and solutions.
  • Complexity: slides, exercises, and solutions.

Since there will be a lot of examples on the blackboard (especially on integer linear programming) it is strongly recommended that you make your own lecture notes .
For your learning experience, solutions to exercises will always be published some time later than the exercises. There will be solutions for a major part of (but not all) exercises.
The following books are not mandatory but interesting for further reading:

  • The lectures on simulation are based on Simulation modeling and analysis, A.M. Law, McGraw-Hill Higher Education, 2015, ISBN 978-1-259-25438-3 (fifth edition) (you can also use an older edition).
  • Integer Programming, Laurence A. Wolsey, Wiley-Interscience publication, 1998, ISBN 0-471-28366-5.
  • Computers and Intractability: A Guide to the Theory of NP-Completeness. M.R. Garey and D.S. Johnson, W.H. Freeman and Company, New York, 1979, ISBN 0-7167-1044-7.
  • Algorithm Design. John Kleinberg, Eva Tardos, Pearson/Addision Wesley, 2005. ISBN 0-321-29535-8.
Course form:Lectures, self-study, exercises, assignments.
Exam form:In the grading the simulation assignment contributes 50% and the written exam contributes 50%. To get a grade of at least 6 the following is required:
  • Simulation assignment:
    • completeness of the report, this means that it has to contain all the parts given in the workplan
    • You attended the final feedback discussion in person. It is not sufficient if other members of your group attended.
  • Final written exam: minimal required grade: unrounded 5.
Minimum effort to qualify for 2nd chance exam: Additional examination :
  • Minimum required effort:
    • Your final grade is at least 4
    • You received a pass for the milestones of the simulation assignment
    • You attended every milestone meetingĀ in person. It is not sufficient if other members of your group attended.
  • Retake for at most one part (out of simulation assignment and exam):
    • If exam < 5, then retake exam
    • If exam < 6 and retake exam >= 6 would be sufficient, then retake exam
    • Otherwise, either retake exam or repair assignment
    • For repair assignment, permission of teacher required
    • Maximum grade for repair assignment is 7
  • If there are unforeseen extreme circumstances because of which you cannot make a milestone or a meeting, you have to notify the teacher beforehand by e-mail.