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.
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
Dr Xinan Yang
Dr Xinan Yang, email: firstname.lastname@example.org
Miss Claire Watts, Departmental Administrator, Tel. 01206 873040, email email@example.com
|Module is taught during the following terms
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.
- 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.
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.
20 per cent Coursework Mark, 80 per cent Exam Mark
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.
Available to Socrates /IP students spending all relevant terms at Essex.
- 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)