The module aims to provide an understanding at postgraduate level of combinatorial optimisation. It aims to understand the mathematical underpinnings of algorithms commonly used in the solution of mathematical programming models where some or all
of the variables are integer. The focus is on applying such algorithms to solve integer and mixed integer models.
Syllabus
- Scope of integer and combinatorial programming.
- Polyhedral theory.
- General integer programming. Theory of valid inequalities.
- Strong valid inequalities and facets for structured problems.
- Duality and relaxation.
- General integer programming algorithms.
- Special purpose algorithms and their applications.
- Unimodularity.
On completion of the module, students should be able to:
- formulate planning and scheduling problems as integer programs;
- describe feasible sets as polyhedra using facets, rays and vertices;
- generate valid inequalities for feasible sets;
- use linear programming relaxation and duality to generate upper bounds for integer programs' objective values;
- solve integer programs with cutting-plane algorithms;
- solve integer and mixed integer programs with Branch-and-Bound;
- apply Benders' decomposition algorithm to mixed integer programs.
- Module Supervisor: Georgios Amanatidis