Discrete Optimisation

Discrete optimization is about the problem of finding a best solution among a (finite) set of feasible solutions. A well-known example is the traveling salesman problem, where we are asked to find a shortest tour in a graph visiting every node exactly once.

This course is an introduction to the area, focusing on fundamental methods like linear programming and its theoretical framework (polyedra, integrality, etc.).

The following topics will be covered:

- Convex sets and their structure.

- Polyhedra, cones, and their structure.

- Linear programming, the simplex method, interior-point methods.

- Systems of linear inequalities, Fourier-Motzkin elimination.

- Farkas's lemma, linear programming duality.

- Several applications and examples: flows in networks, matrix games, bipartite matching, etc.

The final grade of the course consists of the following components:

- Written exam (100%)

Resit/ Repair opportunities:

In case of an insufficient result, repair opportunities may be offered in accordance with TER Implementation Regulations Art 5, sub 5., for:

- Written exam: written resit

Disclaimer: information may change depending on unforeseen circumstances or measures (see: TER Art 29, sub 4).