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, (ii) discussion of modern research implications, (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. Lectures are used to develop the mathematical concepts and ideas. But we augment the lecture with quizzes designed to encourage student interaction. These quizzes will reinforce your understanding and will inspire you to raise questions. As parts of the module are fairly close to the research, a small number of research papers could also be discussed in due course. 

An online service will be used as a discussion forum for the module. 

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

Supplementary

• Linear and nonlinear programming.

  Luenberger, David G.,

  5th ed. 2021 /, Springer

• Introduction to mathematical programming. Operations research. Volume 1

  Winston, Wayne L.

  4th ed., Pacific Grove, CA : Thomson/Brooks/Cole

• Introduction to operations research

  Hillier, Frederick S.,

  Eleventh edition., McGraw-Hill Education

• Operations research : an introduction

  Taha, Hamdy A.,

  Tenth edition, global edition., Pearson Education Limited,

• The Price of Robustness

  Bertsimas, Dimitris ; Sim, Melvyn;

  Operations Research

• When Deep Learning Meets Polyhedral Theory: A Survey

  Joey Huchette Gonzalo Muñoz Thiago Serra Calvin Tsay

Module leaders

Dr Dario Paccagnan
Professor Ruth Misener