Course ObjectiveA student who successfully completes the course will have an
understanding of the techniques of combinatorial optimization and
integer programming, and be ready to apply them to problems encountered
Course Content* The notion of efficiency in algorithms; distinguishing between
tractable and computationally "hard" problems.
* The correctness and efficiency of key algorithms in combinatorial
optimization will be shown rigorously. Problems studied will include:
minimum spanning tree, maximum flow, minimum cost flow, and matching.
* Formulation of problems as integer programs; the notion of the
strength of a formulation; the central role of integral formulations.
* The main techniques and theory used in commercial integer programming
solvers such as Gurobi will be investigated in detail. A main focus will
be on the powerful cutting-plane method.
* Column generation, Lagrangian relaxation, modelling of
disjunctions,and other problem-tailored techniques will be discussed.
* Experience in the use of integer programming solvers will be gained.
* Basic knowledge of Python will be gained.
Teaching MethodsLectures (4 hours/week) and Tutorials (2 hours/week). In tutorials,
exercises on the theory as well as programming exercises will be
Method of AssessmentTheory assignments - group assessment
Programming assignments - group assessment
Final exam – individual assessment
Entry RequirementsCourses in Linear Algebra and Linear programming.
Additional InformationThe course is suitable to be taken in an exchange program.
Recommended background knowledgeIt is expected that students are familiar with the contents of
Operations Research I - and in particular linear programming - at the
start of the course.
Programming is done in Python. No Python knowledge is needed. However,
some amount of programming experience (in any language) is certainly
|Language of Tuition||English|
|Faculty||School of Business and Economics|
|Course Coordinator||dr. N.K. Olver|
|Examiner||dr. N.K. Olver|
dr. N.K. Olver
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|
This course is also available as: