Week 3 - Mathematical Programming

In this session we will introduce the principles of Mathematical Programming, the science (and art) of mathematically representing decision problems.

Mathematical Programming is used across a range of disciplines to determine optimal solutions to a vast range of decision problems. In principle, it focuses on determining the optimal allocation of limited resources, given a specific quantifiable goal and a set of operational constraints.

The word programming, in this case, does not refer to computer programming, but is rather borrowed from military parlance. Many of the decision problems that were initially studied by mathematical programming pioneers (such as George Dantzig, John Von Neumann, Richard Bellman) were focused on military logistics and training operations.

We could spend a full year studying the various aspects of Mathematical Programming and Optimization, and we would only have managed to scratch the surface. The focus of today’s session, however, is to outline its principles and teach you the basics of expressing decision problems mathematically.

Part 1 & 2 - Introduction to Model Building (The Blending Problem) and the Transportation Problem (revisited)

View in Panopto

Part 3, 4, & 5 - The Geometric Method, Symbolic Formulations and Model Types

View in Panopto

Part 6 - Minimum Cost Flow Problems

View in Panopto

Part 7 - Knapsack and Covering Problems

View in Panopto

This week’s seminar introduces Python’s PuLP package - a mathematical programming modeling framework, which we will use in order to develop code-based implementations of our mathematical models, and obtain solutions to problem instances.

Supplement - Solving explicit models using Excel Solver

Our preferred approach for solving optimization models in this module is through the use of Python and PuLP, a technique that is presented in detail in the Jupyter Notebooks that accompany this session. But, to paraphrase a quote by Chase Jarvis (the photographer), the best optimization tool is the one that’s always with you - and in terms of ubiquitousness and availability, nothing compares to Excel.

In this video, He-In introduces the most useful Excel feature that you might have never heard of - the Excel Solver. This is by no means the most capable optimization framework that you will encounter - it effectively only works with explicit model formulations, built using tables.

However, it is an excellent tool that can be used to prototype decision models, and can be very easily incorporated into complex spreadsheet-based models that you might have already developed.

View in Panopto

Download slides
Download spreadsheet

Lecture materials

  • Notebooks

    Jupyter Notebooks that contain interactive demonstrations of the algorithms that were covered in this week’s lecture.

  • Seminar 3

    This seminar provides an introduction to mathematical programming, and their formulation and solution in Python.

  • Tutorial 3

    Tutorial questions relating to the materials covered in this week’s lectures.