Course ObjectiveIn this course you will learn how to develop efficient algorithms for
solving fundamental optimization problems in operations research.
The objectives of the course are to:
- learn about fundamental optimization problems (Scheduling, vehicle
routing, facility location, network design, ...)
- learn algorithms for solving these problems
- learn to prove performance guarantees (running time, approximation
- apply the theory by implementing some of these algorithms.
- construct and implement (in Python) your own algorithms for
Course ContentTopics that will be covered in the course are:
- Scheduling problems, routing problems, facility location problems.
- Integer linear programming, dynamic programming, local search
algorithm, randomized algorithms.
- Theoretical performance guarantees: approximation ratio, polynomial
- Computational complexity theory and hardness of approximation.
- Algorithms for optimization problems in general.
Teaching MethodsLectures (4hours) and tutorials (2hours). Attendance is not compulsory.
Method of AssessmentThe final grade is determined by a written exam (60%) and group
assignments (40%). In the assignment you will apply the theory and
implement algorithms for optimization problems. We use Python for this.
Entry RequirementsBasic knowledge of graph theory and linear programming. Basic
programming skills, preferably Python. If you have experience with other
languages (java, R, Matlab, ...) then Python will be easy to learn.
LiteratureWe use the following book which is freely available for download.
Lecture notes covering the relevant chapters are available on Canvas.
- D.P. Williamson and D.B. Shmoys, The Design of Approximation
Algorithms, Cambridge University Press, 2011.
A substantial part of the course is based on additional material which
will be provided through Canvas. See also
https://personal.vu.nl/r.a.sitters/CO_MOR/ for the latest information.
Target AudienceAnyone with sufficient pre-knowledge and an interest in algorithms for
combinatorial optimization problems in Operations Research.
Additional InformationSee https://personal.vu.nl/r.a.sitters/CO_MOR/ for the latest
information on the course.
Recommended background knowledgeBasic knowledge on graph theory, linear programming, and combinatorial
optimization is assumed. For example, the bachelor courses Operations
Research 3 (SBE) and Combinatorial Optimization for FEW (X_401067) each
provide sufficient pre-knowledge.
|Language of Tuition||English|
|Faculty||School of Business and Economics|
|Course Coordinator||dr. ir. R.A. Sitters|
|Examiner||dr. ir. R.A. Sitters|
dr. ir. R.A. Sitters
You need to register for this course yourself
Last-minute registration is available for this course.
|Teaching Methods||Seminar, Lecture, Computer lab|
This course is also available as: