Back to the Main Page

Linear and Discrete Optimization (COMP4041-LDO)

General Information:

The information here corresponds to Semester 1 of the academic year 2024-2025.

See the Module Specification.

See the Reading List.

See this video giving an overview of the module.

IMPORTANT: The first teaching event of this module is the Computing session in the first week of the semester and can be conducted online. This Computing session will include a taster activity for those that are already enrolled in the module or are considering taking this module. I am also usually available in the Teams space for the module during the time of the computing session to answer questions about the module or to enrol you in Moodle. The taster activity will be available in Moodle before the session (you can self-enrol in Moodle to have a look at the materials).

If you are considering taking this module or course, but need more information to make your decision, you are very welcome to join the first lecture which will give you a good idea about the topics in the module and the type of assessment in this module including sample of past students work and feedback. Alternatively, please contact me if you want to know more about the module.

CONTEXT: This module is related to other modules in the theme 'AI, Modelling and Optimization' in the School of Computer Science. In the COMP4041-LDO module we learn how to write an solve mathematical models of optimization problems like bin packing and travelling salesman. When the problem is not too large, mathematical optimization can be used to find the actual optimal solution to the problem. But when the problem is too large, these mathematical optimization methods might take too long time and hence other search techniques (e.g. heuristics) like those studied in the others modules can be used. However, those heuristic search techniques cannot guarantee to find the actual optimal solution to the problem, but a good enough quality solution is shorter computation times. The techniques studied in the COMP4041-LDO module are the base for developing and understanding optimization and is core knowledge for anyone interested in this field. Even if you are developing heuristic algorithms, it is essential to understand mathematical optimization.

There are various onlive videos about optimization, for example What is Optimization? and Objective Functions and Decision Variables, but please note that other videos in that series are not relevant to the content of this course. This other short video gives an overview of how optimization is relevant to business. Linear and Discrete Optimization, the topic of this module, are techniques within the wider field of Operations Research, this video gives an overview of OR.

An example of the type of optimization problems covered in this module is the travelling salesman problem. For this and other optimization problems, the module covers formulation and solution techniques. You might also want to read this student's reflection about operations research. However, note that this module focuses on optimization, one of the many methods within operations research.

Read about how Google uses Optimization and other Advanced Analytics techniques in order to achieve their mission.

This postgraduate module looks into modelling and optimization techniques, covering the understanding and development of formal optimization models and then developing the computational solutions using existing solvers and/or computer programming for solving real-world operational problems. There is maths in this module, but not too complex, only linear algebra. The module is taught so that students can progress in their understanding of algebraic models and their implementation in spradsheet and script-type solvers to find optimal solution(s) to the given optimization problem.

This page gives only an overview of the module. All the materials including lecture notes, coursework, feedback, etc. are available on the Moodle Learning Enviroment for students enrolled in the module.

Assessment:

The learning outcomes of this module are assessed by means of two components in which students practice every week the understanding, formulation, and implementation of optimization models expressed with linear algebra, and solved with spreadsheet and algebraic solvers. The continuous practice in each week is assessed with in class tests and then students undertake a coursework by the end of the course.

Coursework (70%)

The coursework involves the modelling and solution of real-world optimization problems. There is also a test associated to the coursework.

Inclass Tests (30%)

Series of weekly online tests based on the workshops of the module.