MA306-7-AU-CO:
Combinatorial Optimisation
2024/25
Mathematics, Statistics and Actuarial Science (School of)
Colchester Campus
Autumn
Postgraduate: Level 7
Current
Thursday 03 October 2024
Friday 13 December 2024
15
03 May 2024
Requisites for this module
(none)
(none)
(none)
(none)
(none)
DIP G20109 Optimisation and Data Analytics,
MSC G20312 Optimisation and Data Analytics,
MPHDG20048 Operational Research,
PHD G20048 Operational Research
Combinatorial optimization is one of most active areas of discrete mathematics and deals with optimization in domains where (some or all of) the variables are integral. The main motivation is that a plethora of real-life problems can be modelled as abstract combinatorial optimization problems. The module focuses on problems that can be formulated as integer or mixed integer linear programs and on the algorithms one can apply to solve such programmes, as well as on the underlying theory.
The aims of this module are:
- To introduce classic discrete optimization problems, like scheduling, the traveling salesman problem, and set covering, through the lens of integer linear programming.
- To present polyhedral theory and equip the students with the tools to understand the underlying connections between the mathematical theory and the algorithms used to solve integer linear programs.
- To provide students with an understanding of the main algorithmic techniques for solving (mixed) integer linear programs, as these are often the building blocks of the state-of-the-art approaches used today to deal with massive instances.
By the end of the module, students will be expected to:
- formulate a wide range of combinatorial optimization problems as integer programs;
- describe feasible sets as polyhedra using facets, extreme points and extreme rays;
- identify and generate valid inequalities for feasible sets;
- use linear programming relaxation and duality to generate bounds for integer programs' objective values;
- solve integer programs with cutting-plane algorithms;
- solve integer and mixed integer program with Branch-and-Bound;
- apply Benders' decomposition algorithm to mixed integer programs.
Indicative syllabus
- Scope of integer and combinatorial programming: Modelling with integer variables.
- Pre-processing: Balas’s 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 algorithms, Branch-and-Bound.
- Special purpose algorithms for Mixed Integer Programming: Benders decomposition.
Teaching in the department will be delivered using a range of face to face lectures, classes and lab sessions as appropriate for each module. Modules may also include online only sessions where it is advantageous, for example for pedagogical reasons, to do so.
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: In-Person, Open Book (Restricted), 120 minutes during Summer (Main Period)
|
| Exam |
Reassessment Main exam: In-Person, Open Book (Restricted), 120 minutes during September (Reassessment 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.
Prof Abdellah Salhi
maths@essex.ac.uk
No
No
No
Dr Yinghui Wei
University of Plymouth
Available via Moodle
Of 35 hours, 33 (94.3%) hours available to students:
2 hours not recorded due to service coverage or fault;
0 hours not recorded due to opt-out by lecturer(s), module, or event type.
* Please note: due to differing publication schedules, items marked with an asterisk (*) base their information upon the previous academic year.
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.