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.