The Pain of Shopping with a Data Scientist

The setup

Chris Albon tweeted an image of an undirected graph that he used to justify the number of cables he needed to his partner. She of course responded he was a nerd (subtext). I can only assume that her nerd-shaming of Albon and his lack of time are probably the reasons why he didn’t take this to the next level: A linear programming problem made to minimize the amount of money spent on cables!

Once you’re done reading this post, show it to your significant other and watch them roll their eyes in exasperation at your ridiculous need to turn even the simplest of everyday tasks into a complex problem worthy of that chip on your shoulder!

Modeling it mathematically

My interpretation of the real world version of this problem (the best solutions entail avoiding any collaboration with the actual stakeholder) is as follows:

Minimize the amount of money we spend on cables subject to the following constraints/assumptions:

  1. We must have at least one cable to connect every device to the laptop.
  2. Different devices and needs behoove the use of different lengths of cords.
  3. Costs fluctuate as a function of the cord length

Next we set up a linear programming model in Excel. Why Excel? Because it’s super easy for prototyping these simple models. This is the full mathematical formulation:

Objective function

Minimize

F = 10 * (lightning_1 + microusb_1 + usb_1 + usbc_1) + 15 * (lightning_3 + microusb_3 + usb_3 + usbc_3) + 20 * (lightning_6 + microusb_6 + usb_6 + usbc_6)

Inputs

These follow the pattern of "[connector type]_[length in feet]"

  • lightning_1
  • lightning_3
  • lightning_6
  • microusb_1
  • microusb_3
  • microusb_6
  • usb_1
  • usb_3
  • usb_6
  • usbc_1
  • usbc_3
  • usbc_6

Cost Assumptions 

  1. Each one foot connector has a unit cost of $10
  2. Each three foot connector has a unit cost of $15
  3.  Each six foot connector has a unit cost of $20

Device connectors 

power_supply_connectors = usbc_6

ipad_connectors = lightning_ 1 + lightning_ 3 + lightning_ 6

iphone_connectors = ipad_connectors

android_connectors = microusb_ 1 + microusb_3 + microusb_6

camera_connectors = microusb_3 + microusb_6

battery_usb_connectors = usb_3 + usb_6

battery_usbc_connectors = usbc_3 + usbc_6

battery_connectors = battery_usb_connectors + battery_usbc_connectors

hd_connectors = usbc_3 + usbc_6

Constraints

  1. All input variables are integers
  2. Each device connector must be >= 1 with the exception of the battery_usb_connectors and battery_usbc_connectors (because they are represented by battery_connectors).
  3. The power connector must be 6 feet. I mean seriously.
  4. The iPad/iPhone connectors can be 1, 3, or 6 feet long.
  5. The Android connector can be 1, 3, or 6 feet long.
  6. The camera connector must be 3 or 6 feet long.
  7. The battery connector must be 3 or 6 feet long.
  8. The hard drive connector must be 3 or 6 feet long.

That's all there is to it! We next just translate this model into Excel like so (the optimized result of running the model is pictured):

Thank goodness we did this! Now we know that we will need to buy one 6-foot usbc cable, a 3-foot micro-usb cable, and a 1-foot lightning cable to connect all of our devices. The minimum amount we could possibly spend to meet our criteria is $45 (plus tax and s/h).

Making it a even more complicated

Just to show how we might extend this, what if Albon wanted to use all of his USBC ports on his MBP? We could add the following constraints to the model and then solve

  1.  The number of connectors purchased must be <= the number of devices that can use it.
  2. We must be able to use all four of the usbc ports on Albon's MBP simultaneously. 

In order to do this model must get much more complex. We now need our inputs to be essentially assigning each cable a device to be used on as our inputs (the yellow boxes below). We still keep the top portion of our spreadsheet that indicates if each device has at least one sufficient cable. Conceptually though we are saying "Assign connectors to be used simultaneously with each other on separate devices so that four connectors could be utilized at once and make sure that whatever assignment we come up with enables us to connect all devices to Albon's MBP somehow." 

On top of this we could add on one last constraint: We need to always be able to plug in the power supply and the HD.

Now the minimum cost to meet all of these constraints would be $65 and we would have the power supply and HD plugged in (as required) as well as the iPad and the Android device. If different combinations don't make sense you could add even more constraints to make this as complicated as your little heart desires!

I'm not going to convert this more complicated model to its full mathematical definition because I'm laz... err... I mean... It is obvious how to convert this model to its formal mathematical definition so it is left as an exercise to the reader. Ahem. 

Wrapping up

To summarize, we've seen how we can take a very simple problem and solve in the most pedantic way possible using techniques from Operations Research. We started out with the simplest very complicated solution and eventually moved to a very complicated complicated solution.

In all seriousness, linear programming is a very powerful tool. In our final model, we actually end up with a recommendation of which specific items we should be able to plug in at once. The entire motivation behind that suggestion as well we see are just a series of linear mathematical relationships used to minimize the single objective function of cost.

You can download the Excel file from github here:

https://github.com/jcbozonier/research/blob/master/excel/Cable_models.xlsx

You will need to have the solver add-in for Excel turned on.


Enjoy your loved ones' eye rolls!