Session 4 - Mathematical Programming

Session 4 - Mathematical Programming #

Dr Panagiotis Angeloudis

Banner

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 several 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 instead 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. We will also be introducing Python’s PuLP package - a mathematical programming modelling framework, which we will use in order to transliterate our mathematical models into code, and obtain solutions.

Part 1 - Modelling Decision Problems #

This video marks our first foray into the solution of mathematical programs - the geometric method can help us understand the mechanics of the solution techniques that are used by optimization algorithms.

We then examine the blending problem, disguised as a school bus fleet selection exercise. Starting with a problem statement, we will discuss how to identify the various components of our optimization model and how these will be translated into a mathematical formulation.

Finally, we can practice our new model-building skills with a slightly larger problem that we also happen to know already very well. We will therefore revisit the Transportation Problem, which we will as a mathematical program.

Download slides

Part 2 - Mathematical Programming Principles #

So far, we have used explicit formulations to define our mathematical models, as we list individually every single variable and parameter value. To ensure that we can use this framework flexibly, and with much more complex problems, we will now introduce the principles of symbolic program formulations, where the mechanics and logic of the model are separated from individual problem instances.

To demonstrate how the symbolic formulations work, we will translate our previous transportation and blending model formulations into their formal, symbolic equivalents.

Finally, we discuss the different types of decision variables, objective functions and constraints that we can use when developing our models, and the implications of our choice in the overall classification of our model, and the solution approach that we might need to use.

Download slides

Part 3 - Optimisation of Logistics Processes #

The Transportation Problem captures flows between origins and destinations, but under the assumption that these are directly connected. The Transhipment Problem adds another layer of decision-making in this process, through the incorporation of intermediate hubs that can be used for interim storage, or to act as bridges between different stages of the journey. This is otherwise called the Minimum Cost Flow problem (MCF) and is applicable in a wide range of engineering applications.

In this part, we present the explicit and symbolic MCF formulations, which are used as the basis for the development of a mathematical model that could be used to obtain the shortest path between two nodes in a network.

While an algorithm that relies on such a model would perform a lot worse than a purpose-built approach such as Dijkstra’s or A*, it can serve as a foundation for more complex decision processes that incorporate an element of pathfinding in their formulation.

Finally, we introduce the Knapsack and Covering problems, which we will also revisit later in our course in the sessions related to Public Transport and Freight Distribution.

Download slides

Jupyter Notebooks #

This week’s notebooks focus on the use of PuLP - a Python-based mathematical programming framework. As we will not be going into detail regarding the mechanics of the algorithms used to solve mathematical programs in this module, PuLP and Solver are the only means that we will have at our disposal to solve the problems that we encounter.

Notebook 4.1 - Introduction to PuLP #

In this notebook we are going to introduce a Python package called pulp (PuLP), which we can use to represent and solve optimization problems. We will be starting with the simple two-variable model that we discussed in Part 3 of this session

Notebook 4.2 - Solving the transportation model using PuLP (explicit version) #

We are now going to demonstrate the use of PuLP with a slightly larger problem. For this notebook, we will be considering the explicit transportation model formulation that we discussed in Part 2 of our session.

Notebook 4.3 - Solving the transportation model using PuLP (symbolic version) #

By now we have established that explicit models are not at all practical, and always good to avoid as much as possible - whether we are formulating a model using pen and paper, or with a modeling framework. This notebook demonstrates how we can implement a symbolic model using PuLP.

Notebook 4.4 - Solving Minimum Cost Flow (Transhipment) Problems using PuLP #

We can now try to model a more complex problem - in this notebook we will be looking at the symbolic version of the Transhipment or Minimum Cost Flow Problem, building on top the formulation that we developed in the previous notebook.

Notebook 4.5 - Solving Minimum Cost Flow (Transhipment) Problems using NetworkX and OR-Tools #

This notebook introduces two further approaches that we could use to solve the MCF model - the first involves NetworkX (which we know how to use already), while the second uses Google’s OR Tools - which has an MCF-specific solver which allows us to model problem instances without having to also build a new formulation.

Notebook 4.6 - Shortest paths using PuLP #

As we discussed in Part 6 of our session, we can repurpose our MCF formulation to obtain the shortest paths in a network. This notebook demonstrates how.

Notebook 4.7 - The Knapsack Problem #

We have now covered all the PuLP modeling features that we are going to need for this module. This notebook presents an implementation of our knapsack model.

Notebook 4.8 - The Covering Problem #

And the final notebook for this series focuses on the covering problem. We also show how to obtain the values of specific decision variables.

Running the notebooks #

You can download a zip file containing all the notebooks that we covered in this session from the link below:

Download notebooks (Box)

Tutorial session #

Tutorial 4 - Questions

Tutorial 4 - Answers

Files #

You can find a list of all files that we used this week here (Box).