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

- 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.

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.

Bibliography

  • Recommended Reading:
  • Laurence A. Wolsey, Integer Programming, Wiley & Sons, Inc., 1998
  • G. L. Nemhauser & L. A. Wolsey, Integer and Combinatorial Optimization, Wiley Interscience (1988). This book is expensive - do not buy your own copy.
  • Supplementary Texts:
  • H. P. Williams, Model Building in Mathematical Programming (3rd edition), Wiley Interscience (1987)
  • R. G. Parker & R. L. Rardin, Discrete Optimization, Academic Proess (1988)
  • A. Schrijver, Theory of Linear and Integer Programming, Wiley Interscience (1986)
  • R. S. Garfinkel & G. L. Nemhauser, Integer Programming, Wiley Interscience (1972)
  • C. H. Papadimitriou & K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall (1982)
  • E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan & D.B. Shmoys, The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley Interscience (1985)
  • C. H. Papadimitriou, Computational Complexity, Addison Wesley (1994)

Further information