Optimisation and Heuristics

Optimisation, sometimes called mathematical programming, has applications in many fields, including operational research, computer science, statistics, finance, engineering and the physical sciences.

Commercial optimisation software is now capable of solving many industrial-scale problems to proven optimality. On the other hand, there are still many practical applications where finding a provably-optimal solution is not computationally viable. In such cases, heuristic methods can allow good solutions to be found within a reasonable computation time.

The module is designed to enable students to apply optimisation techniques to business problems. Building on the introduction to optimisation in MSCI 502 and/or MSCI 519, students will be introduced to different problem formulations and algorithmic methods to guide decision making in business and other organisations.

Learning outcomes

By the end of the module you should be able to:

  • know how to formulate problems as mathematical programs and solve them
  • be aware of the power, and the limitations, of optimisation methods
  • be able to carry out sensitivity analysis to see how robust the recommendation is
  • be familiar with commercial software such as MPL, LINDO and EXCEL SOLVER
  • be aware of major heuristic techniques and know when and how to apply them

Outline lecture plan

  • Linear programming (five lectures and two workshops)
  • Non-linear programming (two lectures)
  • Integer and mixed-integer programming (three lectures and one workshop)
  • Dynamic programming (two lectures and one workshop)
  • Heuristics (four lectures)

Assessment

Exam (70%) – there will be an open-book exam where three questions are to be answered from a choice of questions in two hours 45 minutes (including 15 minutes reading time). The workshop questions will form a good preparation for the exam.

CWA (30%) – there will be a coursework exercise which will include some manual work and some use of software.

Timing

Lent Term

Reading and lecture notes

Lecture notes will be provided for the course, so there will not be any need to purchase a particular textbook. However, the following books may be useful:

  • HP Williams (2013) Model Building in Mathematical Programming (5th edition). Wiley. ISBN: 978-1-118-44333-0 (pbk).
  • J Kallrath & JM Wilson (1997) Business Optimisation Using Mathematical Programming. Macmillan. ISBN: 0-333-67623-8.

In addition, many introductory text books on Management Science or Operational Research also have good chapters on Mathematical Programming, for example:

  • WL Winston (2004) Operations Research - Applications and Algorithms (4th edition).
  • DR Anderson, DJ Sweeney & TA Williams & M. Wisniewski (2008) An Introduction to Management Science. Cengage Learning. ISBN 0324202318

For the Heuristics section, one useful book is:

  • Edmund K. Burke & Graham Kendall (Editors) (2005) Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer, New York.

Module tutor

Professor Adam Letchford