MA306-7-AU-CO:
Combinatorial Optimisation
2020/21
Mathematics, Statistics and Actuarial Science (School of)
Colchester Campus
Autumn
Postgraduate: Level 7
Current
Thursday 08 October 2020
Friday 18 December 2020
15
15 July 2020
Requisites for this module
(none)
(none)
(none)
(none)
(none)
DIP GN1309 Mathematics and Finance,
MSC GN1312 Mathematics and Finance,
MSC GN1324 Mathematics and Finance,
DIP G20109 Optimisation and Data Analytics,
MSC G20312 Optimisation and Data Analytics,
MPHDG20048 Operational Research,
PHD G20048 Operational Research
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.
No information available.
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, extreme points and extreme rays;
- 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.
Syllabus
- Scope of integer and combinatorial programming: Modelling with integer variables.
- Pre-processing: Balas' constraint disaggregation procedure.
- Polyhedral theory: Valid inequalities; Facet constraints; Convex hull of integer solutions.
- LP relaxation of integer programming problems.
- General integer programming algorithms: Cutting plane, Branch and Bound algorithms.
- Special purpose algorithms for Mixed Integer Programming: Benders decomposition.
- Unimodularity.
Teaching will be delivered in a way that blends face-to-face classes, for those students that can be present on campus, with a range of online lectures, teaching, learning and collaborative support.
- Williams, H. P. (2015) Model building in mathematical programming, Chichester: Wiley.
- Nemhauser, George L.; Wolsey, Laurence A. (1999) Integer and combinatorial optimization, Chichester: Wiley.
- Wolsey, Laurence A. (2021) Integer programming, Hoboken, NJ: 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 |
Coursework weighting |
| Coursework |
Assignment 1 |
|
|
| Coursework |
Assignment 2 |
|
|
| Exam |
Main exam: 180 minutes during Summer (Main Period)
|
Exam format definitions
- Remote, open book: Your exam will take place remotely via an online learning platform. You may refer to any physical or electronic materials during the exam.
- In-person, open book: Your exam will take place on campus under invigilation. You may refer to any physical materials such as paper study notes or a textbook during the exam. Electronic devices may not be used in the exam.
- In-person, open book (restricted): The exam will take place on campus under invigilation. You may refer only to specific physical materials such as a named textbook during the exam. Permitted materials will be specified by your department. Electronic devices may not be used in the exam.
- In-person, closed book: The exam will take place on campus under invigilation. You may not refer to any physical materials or electronic devices during the exam. There may be times when a paper dictionary,
for example, may be permitted in an otherwise closed book exam. Any exceptions will be specified by your department.
Your department will provide further guidance before your exams.
Overall assessment
Reassessment
Module supervisor and teaching staff
Prof Abdellah Salhi, email: as@essex.ac.uk.
Professor Abdel Salhi & Dr Dmitry Savostyanov
Professor Abdel Salhi (as@essex.ac.uk), Dr Dmitry Savostyanov (d.savostyanov@essex.ac.uk)
No
No
No
Prof Fionn Murtagh
University of Huddersfield
Professor of Data Science
Available via Moodle
Of 2029 hours, 0 (0%) hours available to students:
2029 hours not recorded due to service coverage or fault;
0 hours not recorded due to opt-out by lecturer(s).
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.