MA306-7-SP-CO:
Combinatorial Optimisation

The details
2019/20
Mathematical Sciences
Colchester Campus
Spring
Postgraduate: Level 7
Current
Monday 13 January 2020
Friday 20 March 2020
15
01 October 2019

 

Requisites for this module
(none)
(none)
(none)
(none)

 

(none)

Key module for

MSC G10112 Mathematics,
MSC G10124 Mathematics,
DIP GN1309 Mathematics and Finance,
MSC GN1312 Mathematics and Finance,
MSC GN1324 Mathematics and Finance,
DIP G20109 Statistics and Operational Research,
MSC G20312 Statistics and Operational Research

Module description

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.

Module aims

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.

Module learning outcomes

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 information

No additional information available.

Learning and teaching methods

There are 5 lectures and two classes in every fortnight. There will be regular assessed material at postgraduate level which will be discussed in one of the fortnightly classes. In the Summer term 3 revision lectures are given.

Bibliography

  • Winston, Wayne L. (c2004) Operations research: applications and algorithms, Australia: Thomson Brooks/Cole.
  • Wolsey, Laurence A. (c1998) Integer programming, New York: Wiley. vol. Wiley-Interscience series in discrete mathematics and optimization
  • Nemhauser, George L.; Wolsey, Laurence A. (c1988) Integer and combinatorial optimization, New York: Wiley. vol. Wiley-Interscience series in discrete mathematics and optimization
  • Williams, H. P. (2015) Model building in mathematical programming, Chichester: Wiley.

The above list is indicative of the essential reading for the course. The library makes provision for all reading list items, with digital provision where possible, and these resources are shared between students. Further reading can be obtained from this module's reading list.

Assessment items, weightings and deadlines

Coursework / exam Description Deadline Weighting
Coursework Coursework 1 14/02/2020
Coursework Coursework 2 20/03/2020
Exam 120 minutes during Summer (Main Period) (Main)

Overall assessment

Coursework Exam
20% 80%

Reassessment

Coursework Exam
0% 100%
Module supervisor and teaching staff
Prof Abdel Salhi, email as@essex.ac.uk
Professor Abdel Salhi (as@essex.ac.uk)

 

Availability
No
No
No

External examiner

Prof Fionn Murtagh
Professor of Data Science
Resources
Available via Moodle
Of 38 hours, 38 (100%) hours available to students:
0 hours not recorded due to service coverage or fault;
0 hours not recorded due to opt-out by lecturer(s).

 

Further information
Mathematical Sciences

Disclaimer: The University makes every effort to ensure that this information on its Module Directory is accurate and up-to-date. Exceptionally it can be necessary to make changes, for example to programmes, modules, facilities or fees. Examples of such reasons might include a change of law or regulatory requirements, industrial action, lack of demand, departure of key personnel, change in government policy, or withdrawal/reduction of funding. Changes to modules may for example consist of variations to the content and method of delivery or assessment of modules and other services, to discontinue modules and other services and to merge or combine modules. The University will endeavour to keep such changes to a minimum, and will also keep students informed appropriately by updating our programme specifications and module directory.

The full Procedures, Rules and Regulations of the University governing how it operates are set out in the Charter, Statutes and Ordinances and in the University Regulations, Policy and Procedures.