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.

Pre-requisite Module: MA2008 Linear Algebra II

Recommended Modules: MA2601 Operational Research

1. Understand the basic concepts of linear and nonlinear optimisation

2. Use the Simplex method to solve general linear programming problems and understand its matrix interpretation

3. Construct and solve search trees and branch and bound.

4. Understand the underlying ideas of nonlinear optimisation and the concept of convexity. Be able to use basic solution methods.

5. Apply dynamic programming to deterministic and stochastic problems

6. Demonstrate understanding of basic geometry of polyhedra.

7. Apply Chvatal-Gomory cutting plane algorithm to solve simple integer linear programs.

8. Demonstrate understanding of selected fundamental theorems in discrete geometry.

9. Apply lattice basis reduction algorithms to solve optimisation problems over lattices.

10. To formulate integer programming models for a selection of classical optimisation problems.

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 to support the learning (e.g. videos, exercise sheets, lecture notes, quizzes)

Students are also expected to undertake at least 100 hours of self-guided study throughout the duration of the module, including preparation of formative assessments.

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.

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;