MA3603: Optimisation
| School | Cardiff School of Mathematics |
| Department Code | MATHS |
| Module Code | MA3603 |
| External Subject Code | 100404 |
| Number of Credits | 20 |
| Level | L6 |
| Language of Delivery | English |
| Module Leader | Dr Jonathan Thompson |
| Semester | Autumn Semester |
| Academic Year | 2022/3 |
Outline Description of Module
This double module is an introduction to the mathematical foundations of optimisation and integer programming. In these topics one seeks to minimize or maximize a real function of real or integer valued variables, subject to constraints on the variables (equations or inequalities that need to be satisfied by all solutions). The main goals of the module are to describe the main mathematical properties of the optimisation problems, to introduce algorithms for finding optimal solutions and to show how these algorithms can be applied to a selection of classical optimisation problems.
Recommended Modules: MA0261 Operational Research
On completion of the module a student should be able to
-
Understand the basic concepts of linear and nonlinear optimisation
-
Use the Simplex method to solve general linear programming problems and understand its matrix interpretation
-
Construct and solve search trees and branch and bound.
-
Understand the underlying ideas of nonlinear optimisation and the concept of convexity. Be able to use basic solution methods.
-
Apply dynamic programming to deterministic and stochastic problems
-
Demonstrate understanding of basic geometry of polyhedra.
-
Apply Chvatal-Gomory cutting plane algorithm to solve simple integer linear programs.
-
Demonstrate understanding of selected fundamental theorems in discrete geometry.
-
Apply lattice basis reduction algorithms to solve optimisation problems over lattices.
-
To formulate integer programming models for a selection of classical optimisation problems.
How the module will be delivered
Modules will be delivered through blended learning. You will be guided through learning activities appropriate to your module, which may include:
- Weekly face to face classes (e.g. labs, lectures, exercise classes)
- Electronic resources that you work through at your own pace (e.g. videos, exercise sheets, lecture notes, e-books, quizzes)
Students are also expected to undertake self-guided study throughout the duration of the module.
Skills that will be practised and developed
Knowledge and Understanding:
Various types of optimisation problems including linear and non-linear. Solutions methods for linear and integer programs. Understanding of how to apply dynamic programming in various situations including stochastic cases. An understanding of the limitations of solution methods.
The basic properties of convex sets, basic polyhedral geometry, fundamentals of computational discrete geometry, algorithms for solving integer programming problems and problems on lattices.
Skills:
Optimisation formulations for a selection of basic scientific and engineering problems. Problem solving, logical thinking.
Assessment Breakdown
| Type | % | Title | Duration(hrs) |
|---|---|---|---|
| Exam - Autumn Semester | 100 | Optimisation | 3 |
Syllabus content
Introduction to optimisation including linear and nonlinear models
Linear programming, Simplex Algorithm, duality, parametric programming, Branch and Bound.
Nonlinear optimisation, convexity, gradient methods, Lagrange Methods.
Dynamic programming. Deterministic and stochastic cases.
Geometry of Polyhedra; Farkas-Minkowski-Weyl theorem; Hilbert bases; Chvatal-Gomory cutting planes; Convex sets and lattices, Minkowski's fundamental theorems;
Lattice reduction algorithms: Gauss and LLL algorithm;