U of Nott CS & IT COL Research Lab


Last Update: 18 November 2021

Back to the Main Page

Linear and Discrete Optimization (COMP4041-LDO)

General Information:

The information here corresponds to Semester 1 of the session 2021-2022.

See the Module Specification.

See the Reading List.

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 an 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 in your 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/G54LDO module are the base for developing and understanding optimization and is core knowledge for anyone interested in this field. Even if you are developing heuristics, it is essential to understand mathematical optimization.

Linear and Discrete Optimization, the topic of this module, are techniques within the wider field of Operations Research, to get an idea see this video. 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. See a sample of the lecture notes. 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.

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.

Content of the Module:

The module covers the following topics: Linear Programming, Modelling and Optimization Software, Post-optimality Analysis, Integer Programming, Mathematical Programming Modelling Techniques, Multi-objective Optimization, Algorithms for LP and IP Models, Dynamic Programming.

Assessment:

Examination (50%)

The exam is based on problem modelling and solving, more details will be given during the lectures.

Coursework (25%)

The coursework involves the modelling and solution of real-world optimization problems.

Inclass Exam (25%)

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