# Module Details

## MA306-6-SP-CO: Combinatorial Optimisation

Note: This module is inactive. Visit the Module Directory to view modules and variants offered during the current academic year.

Year: 2016/17
Department: Mathematical Sciences
Essex credit: 15
ECTS credit: 7.5
Available to Study Abroad / Exchange Students: Yes
Full Year Module Available to Study Abroad / Exchange Students for a Single Term: No
Outside Option: Yes
Pre-requisites: MA114 and MA205
Co-requisites:

Staff
Supervisor: Dr Xinan Yang, email: xyangk@essex.ac.uk
Teaching Staff: Dr Xinan Yang, email: xyangk@essex.ac.uk
Contact details: Miss Claire Watts, Departmental Administrator, Tel. 01206 873040, email cmwatts@essex.ac.uk

 Module is taught during the following terms Autumn Spring Summer

### Module Description

The module 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

- Modelling integer and mixed-integer programming problems (Assignment problem, Travelling Salesman problem, Set Covering problem, Knapsack problem etc.).
- Modelling logical statements and constraints using Binary variables.
- Special purpose algorithms and their applications.
- Polyhedral theory.
- Convex hull, strong valid inequalities and facets for structured problems.
- Duality and relaxation.
- General integer programming algorithms (Branch-and-Bound, Gomory’s Cutting Plan).
- Benders’ decomposition and reformulation.
- (probably) 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.

### Learning and Teaching Methods

The module runs at 3 hours per week in the Spring term. There are 5 lectures and one class in every fortnight.
In the Summer term 3 revision lectures are given.

### Assessment

20 per cent Coursework Mark, 80 per cent Exam Mark

### Other details

Information about coursework deadlines can be found in the "Coursework Information" section of the Current Students, Useful Information Maths web pages: Coursework and Test Information

### Exam Duration and Period

2:00 during Summer Examination period.

### Other information

Available to Socrates /IP students spending all relevant terms at Essex.