CloseHelpPrint
Kies de Nederlandse taal
Course module: 35V5A3-B-6
35V5A3-B-6
Combinatorial Optimization
Course info
Course module35V5A3-B-6
Credits (ECTS)6
CategoryBA (Bachelor)
Course typeCourse
Language of instructionEnglish
Offered byTilburg University; Tilburg School of Economics and Management; TiSEM: Econometrics and OR; Econometrics & Operations;
Is part of
B Econometrics and Operations Research
Contact persondr.ir.ing. M.J.P. Peeters
Lecturer(s)
Coordinator course
dr.ir.ing. M.J.P. Peeters
Other course modules lecturer
Lecturer
dr.ir.ing. M.J.P. Peeters
Other course modules lecturer
Lecturer
prof.dr.ir. R. Sotirov
Other course modules lecturer
Academic year2019
Starting block
SM 1
Course mode
Full-time
Remarks-
Registration openfrom 19/08/2019 up to and including 24/01/2020
Aims
  • The student knows a wide scope of combinatorial optimisation models and the corresponding relevant algorithms and heuristics.
  • The student has insight in the complexity of combinatorial problems, especially the difference between 'easy' and 'hard' problems.

Recommended Prerequisites

Lineair Optimization, Advanced Linear Algebra
Content
Many decision problems from practice can be described as combinatorial optimization problems. Typically, these problems have a finite set of possible solutions such that an optimal solution always exists. In general combinatorial optimization problems can be translated to integer linear programming problems (ILP). So one way to solve them is by solving the ILP. Often however, these algorithems are time consuming. For some combinatorial optimization problems (the 'easy' problems) fast solution methods exist while for other problems (the 'difficult' problems) finding the optimal solution is time consuming and only practical achievable if the problem is 'small'. The field of mathematics that formalizes this distinction in 'easy' and difficult' is the complexity theory. For difficult problems one often has to be satisfied with an approximation of the optimal solution. In these cases it is important to have good bounds for the accuracy of the approximate solution.

In this course we will treat the aspects mentioned above as well as a number of concrete problems and solution methods. Among others we treat the easy problems 'shortest path', 'maximal flow' and 'assignment', the difficult problems 'traveling salesman', 'knapsack', 'vehicle routing' and 'truck loading' and the methods 'greedy', 'branch and bound', 'dynamic programming' and 'local search'. Extra attention is paid to scheduling problems. For these problems the aim is to find an optimal scheduling of operations in a production process. On the one hand these problems are clearly applicable while on the other hand they are very illustrative since all aspects of combinatorial optimization appear.

Type of instructions

4 contact hours a week + 2 computerlabs

Type of exams

written exam (90%) + computer assignment (10%)

Compulsory Reading
  1. Handouts (via Blackboard).
Course available for exchange students
Conditions of admission apply
Timetable information
Combinatorial Optimization
Written test opportunities
DescriptionTestBlockOpportunityDate
Schriftelijk 90% / Written 90%EXAM_01SM 1221-01-2020
Written test opportunities (HIST)
DescriptionTest/BlockOpportunityDate
Schriftelijk 90% / Written 90%EXAM_01SM 1113-12-2019
Required materials
-
Recommended materials
-
Tests
Assignment 10%

Written 90%

Final grade

CloseHelpPrint
Kies de Nederlandse taal