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

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.

Modules will be delivered through blended learning. You will be guided through learning activities appropriate to your module, which may include:

• On-line resources that you work through at your own pace (e.g. videos, web resources, e-books, quizzes),
• On-line interactive sessions to work with other students and staff (e.g. discussions, live streaming of presentations, live-coding, group meetings)
• Face to face small group sessions (e.g. tutorials, exercise classes, feedback sessions)

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.

Formative assessment is carried out by means of regular tutorial exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during tutorial classes.  

Summative assessment is by means of the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes. It also allows students to give evidence of the higher levels of knowledge and understanding required for high marks.

The examination paper has a choice of four from six equally weighted questions.

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;
 

An interactive version of this list is now available via our new reading list software: https://whelf-cardiff.alma.exlibrisgroup.com/leganto/public/44WHELF_CAR/lists/6034758420002420?auth=SAML

Schrijver, A. 1986. Theory of Linear and Integer Programming

Williams, H.P. 1993. Model solving in mathematical programming. Wiley. 

Winston, W.L., & Venkataramanan, M.2003. Introduction to mathematical programming. 4th ed. Thomson/Brooks/Cole