MA306-6-AU-CO:
Combinatorial Optimisation

The details
2024/25
Mathematics, Statistics and Actuarial Science (School of)
Colchester Campus
Autumn
Undergraduate: Level 6
Current
Thursday 03 October 2024
Friday 13 December 2024
15
18 March 2024

 

Requisites for this module
MA114 and MA205
(none)
(none)
(none)

 

(none)

Key module for

(none)

Module description

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.

Module aims

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.

Module learning outcomes

By the end of the module, students will be expected to:



  1. formulate a wide range of combinatorial optimization problems as integer programs;

  2. describe feasible sets as polyhedra using facets, extreme points and extreme rays;

  3. identify and generate valid inequalities for feasible sets;

  4. use linear programming relaxation and duality to generate bounds for integer programs' objective values;

  5. solve integer programs with cutting-plane algorithms;

  6. solve integer and mixed integer program with Branch-and-Bound;

  7. apply Benders' decomposition algorithm to mixed integer programs.

Module information

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.

Learning and teaching methods

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.

Bibliography

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

Coursework Exam
20% 80%

Reassessment

Coursework Exam
20% 80%
Module supervisor and teaching staff
Dr Georgios Amanatidis, email: georgios.amanatidis@essex.ac.uk.
Dr Georgios Amanatidis
georgios.amanatidis@essex.ac.uk

 

Availability
Yes
Yes
No

External examiner

Dr Yinghui Wei
University of Plymouth
Dr Murray Pollock
Newcastle University
Director of Statistics / Senior Lecturer
Resources
Available via Moodle
Of 30 hours, 28 (93.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.

 

Further information

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.