Linear and Discrete Optimization
| Code | School | Level | Credits | Semesters |
| COMP4041 | Computer Science | 4 | 20 | Autumn UK |
- Code
- COMP4041
- School
- Computer Science
- Level
- 4
- Credits
- 20
- Semesters
- Autumn UK
Summary
The module provides an entry point to computational optimization techniques, particularly for modelling and solving linear and discrete optimization problems like diet optimization, network flows, task assignment, scheduling, bin-packing, travelling salesmen, facility location, vehicle routing and related problems.
Optimization sits at the interface of computer science and mathematics. Optimization is considered one of the key techniques within the broad spectrum of artificial intelligence methods. Optimization focuses on making decisions instead of predicting or identifying patterns. Optimization is also one of the most important areas within operations research (OR), which is a discipline that uses modelling techniques, analytics and computational methods to solve complex problems in industry and business.
In this module, you will learn to interpret and develop algebraic models for a variety of real-world linear and discrete optimization problems to then use powerful optimization software (linear, integer and mixed-integer solvers) to produce a solution. The module covers topics such as linear programming, integer programming, combinatorial optimization, modelling and optimization software, multi-objective optimization, simplex method, and branch and bound method among others. Optimization technology is ubiquitous in today's world, for applications in logistics, finance, manufacturing, workforce planning, product selection, healthcare, and any other area where the limited resources must be used efficiently. Optimization enables prescriptive analytics to support and automate decision-making.
Target Students
Available to Level 3 and 4 students in the School of Computer Science. This module is not available to students not listed above without explicit approval from the module convenor(s). This module is part of the Artificial Intelligence, Modelling and Optimisation theme in the School of Computer Science.
Classes
In the weekly workshops, students work individually and in small groups on developing models and solutions to optimization problems to practice the concepts covered in the lecture. In the weekly computing session, students take a open book test answering questions about the workshop tasks and extensions to them.
Assessment
- 70% Coursework 1: Spreadsheet and algebraic mathematical programming models to solve an optimization problem, video report and open book test. Reassessment for the module is 100% coursework with an associated test.
- 30% In-class Tests: Several open book tests based on the workshops. Reassessment for the module is 100% coursework with an associated test.
Assessed by end of autumn semester
Educational Aims
To develop an understanding of linear and discrete optimization, one of the most important areas within artificial intelligence and operations research.To develop the skills for modelling a range of optimization problems in business and industry using mathematical programming models.To implement those models using algebraic and spreadsheet optimization solvers to obtain solutions to the corresponding optimization problem.To develop skills for identifying, analysing, modelling and solving real-world linear and discrete optimization problems.Learning Outcomes
Knowledge and Understanding
- Fundamental concepts of linear and discrete optimization from the computer science and mathematical perspectives.
- Algebraic models for linear and discrete optimization problems.
- Post-optimality analysis and multi-objective optimization.
- Simplex method and Branch and Bound method.
Intellectual Skills
- Analytical methods to identify components of optimization problems.
- Developing algebraic and spreadsheet models of optimization problems.
- Reasoning and evaluation of solutions to optimization models.
Professional Practical Skills
- Use of algebraic and spreadsheet optimization software to solve optimization problems in a range of application domains.
- Critical evaluation of computer optimization models and their solutions.
- Application of optimization as an AI technique for decision-making.
Transferable Skills
- Critical thinking
- Problem solving
- Communication skills
- Computational and mathematical skills.