Operations Research

Module aims

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

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

Module syllabus

Introduction: review of mathematical background, optimal decision making processes in design and management. Problems examples.

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.

Pre-requisites

For Computing students C233 - Computational Techniques, there are no pre-requisites for ISE and JMC students.

Teaching methods

Lectures and tutorials.

Tutorials will develop case studies based on the GNU Linear Programming Kit.

Two assessed courseworks will be given throughout the course.

Assessments

*This is a level 6/H course

Reading list

Core

Supplementary

Module leaders

Dr Giuliano Casale