Part 2 — How I applied linear modelling to solve a ‘real life’ problem

In the previous post, I described a data science/modelling situation- I called it a ‘Shopping Problem’. To recap, we broke down this problem in to following components:

(Oh, and I also found a legit mathematical text editor called ‘TexMaker’ so the formulas are easy on the eyes)

Objective

Constraints

Note that there is a third constraint which is a non-negativity constraint. Again, using our intuition, we don’t want to yield negative results for the problem we have.

Intuition/Assumptions.

• Assume minimum of 5 locations per person
• Assume 20 items per person — reason being it makes intuitive sense of 20:5 ratio of items to location

In this series, you will learn how to implement and solve for decision variables using Python NumPy and PuLP modelling library.

This tutorial will go through the following steps:

1. Calculating the efficiencies per individual using NumPy array and linear algebra solver
2. Next we will using PuLP, a linear programming modelling framework to solve for optimum decision variables.

Calculating the efficiencies

We can only come up with optimum solution per person if we have efficiencies calculated per person. To do this we need some historic data (more the better). In our example, consider the data above. We are going to use this to calculate efficiency in terms of time in takes for each person to find/pick and walk to a location.

To do this we must organize our data in matrices:

Solving this using NumPy yields the following results:

Individual 1:

Individual 2:

Let’s interpret the results:

For worker/individual 1, it’s going to take 0.36 minutes to find/pick an item and 1.05 minutes to travel from one location to another. For worker/individual 2, it’s going to take 0.52 minutes to find/pick an item and 0.75 minutes to travel from one location to another.

Based on these calculations, we should update our objective functions. Assume as you keep getting more historic data, these values will keep becoming more accurate.

Here is the updated objective function:

Finding the optimum decision variables

Now that we have updated our objective function to reflect more accurate data, we expect to get more reliable results. This section will focus on plugging in every function we have defined into the modelling framework.

First step is to import necessary libraries:

• PuLP for modelling
• pandas is useful if you want to import csv files for historic data
• numpy to calculate matrices

Then based on your calculations for efficiency and assumptions, define some constants.

Next let’s define the following:

• Linear programming problem and define a name. Our objective is to minimize time — therefore LpMinimize
• The four decisions variables for two individuals for finding/picking and travelling to a location. Here we also define minimums. Based on our assumptions, we define minimum of 5 locations and 20 picks per person.
• Objective function using the constants
• Two constraints that add up to 60 picks and 15 locations.

Alright, almost there. The following functions solve and print the solution.

The modelling framework yeilds the following results:

This is super efficient! Could even grab a coffee while shopping if everything can be completed in 20 minutes!

Some Gotchas and improvements

• One thing you can’t avoid in shopping is the checkout process — to get a accurate time, you can add that on as a constant. This would be the most straightforward way. You can also get creative and try to find an optimum taking into account checkout plus overlapping shopping while one person gets in the line to checkout. Crazy eh?
• Historic data — more you have better it is! You can think about days and times as that could affect the density of the crowd in the supermarket.
• Scalability — What is a better scalable model? Are there thresholds to be considered as we add more people to shop? Do we revise our assumptions based on that?

So…..many….possibilities!