The goal of this course is to study quantitative methods for decision making. The emphasis is on numerical algorithms to solve constrained optimisation programs. The methods studied in the course are applicable to problems arising in many areas, including computer science, economics, logistics, and industrial engineering.
Learning Outcomes - Knowledge and Understanding
To know the specific material covered in the Syllabus, including the ability to do the following:
- To identify application domains for linear programming and game theory
- To classify mathematical programs on the basis of the number and types of their solutions
- To understand solution techniques for linear programs with real and integer-valued variables
- To understand the fundamental notions of duality, degeneracy, and sensitivity
Learning Outcomes - Intellectual Skills
- To model adversarial decision problems using linear programming
- To select an appropriate solution method for a given mathematical program
- To recognize patterns in real-world decision problems that can be modelled using linear programming
- To take resource allocation decisions based on mathematical analysis
- To formulate mathematical programs used for decision-making
- To formulate an adversarial decision problem in terms of a game
Learning Outcomes - Practical Skills
- To solve linear programs using open source software
Part 1: Linear programming (LP)
- Foundations: definitions, basic-feasible solutions, the simplex method, degenerate solutions, two-phase simplex method. duality, shadow prices.
- LP modelling techniques: resource allocation & blending models, operations planning models, shift scheduling models, time-phased models, linearization methods (min-max, min-min, goal programming)
Part 2: Advanced methods
- Integer linear programming: Gomory's cutting plane method for pure and mixed integer linear programming. Search methods; branch-and-bound and branch-and-cut algorithms.
- Game theory: definitions, two person non-cooperative games, saddle points.
For Computing students C233 - Computational Techniques, there are no pre-requisites for ISE and JMC students.
Lectures and tutorials.
Tutorials will develop case studies based on the GNU Linear Programming Kit.
Two assessed courseworks will be given throughout the course.
*This is a level 6/H course