COMP331

Optimisation

Aims

  1. To provide a foundation for modelling various continuous and discrete optimisation problems.
  2. To provide the tools and paradigms for the design and analysis of algorithms for continuous and discrete optimisation problems. Apply these tools to real-world problems.
  3. To review the links and interconnections between optimisation and computational complexity theory.
  4. To provide an in-depth, systematic and critical understanding of selected significant topics at the intersection of optimisation, algorithms and (to a lesser extent) complexity theory, together with the related research issues. ??

Syllabus

  1. Basics: Linear Algebra, Geometry and Graph Theory. (5 lectures)
  2. Linear Programming Basics: Introduction, Definitions, Examples, Geometric and Algebraic views of Linear Programming, Mixed Integer Linear Programming (7 lectures)
  3. Linear Programming: Simplex Algorithm (6 lecture)
  4. Linear Programming: Duality (5 lectures )
  5. Algorithms for important optimisation problems (e.g. optimal trees and paths, network flows). (7 lectures)

Recommended Texts

Reading lists are managed at readinglists.liverpool.ac.uk. Click here to access the reading lists for this module.
Explanation of Reading List:

Learning Outcomes

  • A conceptual understanding of current problems and techniques in the field of optimisation.
  • The ability to formulate optimisation models for the purpose of modelling particular applications.
  • The ability to use appropriate algorithmic paradigms and techniques in context of a particular optimisation model.