- 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 PrerequisitesLineair Optimization, Advanced Linear Algebra
|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 instructions4 contact hours a week + 2 computerlabs
Type of examswritten exam (90%) + computer assignment (10%)
- Handouts (via Blackboard).