Operations Research

Module aims

This module will give you the opportunity to:

  • explore quantitative mathematical methods for taking decisions in the presence of constraints or finite resources
  • learn about linear programming, integer linear programming, robust optimisation, and game theory and their application
  • classify mathematical programs on the basis of the number and types of their solutions
  • implement solution techniques for linear programs with both real and integer-valued variables
  • familiarise yourself with fundamental notions of duality, degeneracy, and sensitivity

Learning outcomes

Upon successful completion of this module you will be able to:

  • classify mathematical programs on the basis of the number and types of their solutions
  • apply linear programming to real-world decision problems with real and integer-valued variables
  • model adversarial decision problems using linear programming
  • select an appropriate solution method or sythesise a new method for a given mathematical program
  • formulate mathematical programs used for decision-making and decision-making under uncertainty
  • formulate an adversarial decision problem in terms of a game

Module syllabus

  • Introduction to linear programming
  • Basic feasible solutions
  • Simplex method
  • Degenerate linear programs
  • Duality and shadow prices
  • Integer linear programming
  • Cutting planes
  • Branch-and bound and branch-and-cut
  • Game theory & robust optimisation

Teaching methods

This module primarily operates as a lecture-style module, but we place significant emphasis on (i) interaction with students during lecture, e.g. via Mentimeter, (ii) discussion of modern research implications, e.g. via research papers that have recently appeared, (iii) a community of learners, e.g. via the Piazza discussion boards,  (iv) open ended coursework that encourages students to try different possibilities, (v) optional hands-on exercises based on the GNU linear programming kit. The traditional lecture format is used to develop the mathematical concepts and ideas. But we augment the lecture with quizzes designed to encourage student interaction. These Mentimeter questions will reinforce your understanding and will inspire you to raise questions. The module is fairly close to the research, so a small number (typically one or two) research papers will be discussed in class.    

Assessments

The module features two courseworks, one for each part covered by the lecturers, to better pace and consolidate the learning of the algorithms and modelling techniques explained in the course. You will be able to work on your own or in small groups, and receive written feedback on each submission. These coursework collectively contribute 20% of the module marks. The remaining 80% will be assessed in a final written exam, which will test the understanding of the methods presented in the course as well as of their underpinning theory.  

There will be detailed feedback on the coursework exercises which will include written feedback on your individual submission and class-wide or written feedback explaining common pitfalls and suggestions for improvement.   

Reading list

Core

Supplementary

Module leaders

Dr Ruth Misener
Dr Giuliano Casale