Whether you love or hate McDonalds a visit almost inevitably crops up every now and again – so recently I challenged myself to use R to maximize my ‘late night’ foodie experience. After all if I’m going to spend money at Ronald’s I may as well get the best possible outcome 🙂

There are of course many dimensions to the McDonalds experience that one could optimize such as:

- never going there in the first place
- minimizing time spent queuing (by forecasting which queue line may go faster);
- minimizing time spent waiting for your order to be prepared (by forecasting which items will be pre-prepared or quick to make);
- minimizing the health / nutritional disbenefits of your order (by making trade-offs between the cost, healthiest and yummiest options).

This post will look at latter option… how to use R to make an order that meets your nutritional requirements whilst minimizing financial costs and constraining the health / nutritional disbenefits.

To perform this in an systematic way I will first frame the challenge as a integer programming problem and then solve it using the Rsymphony package.

**A McDonalds order as an integer linear programming problem**

Integer linear programs (ILPs) have the following form:

**maximize Z** where z = cx (where c is a vector of weights, x is a vector of items)

**subject to:** Ax <= b (where b is a vectors of constraint values on x and A represents a matrix containing the set of weights for each item with respect to that constraint)

**and** x>=0 and a whole number.

**Problem 1 – Stuffing your face in a slightly healthier way**

To applying ILP to our McDonald’s problem we could say: *I want to maximize my calorie intake subject to total cost<= $10 AND <= 2300mg sodium AND <= 25g sugar AND <= 20g trans-fat*.

This means that our **x** vector is the number of each item on the menu that we will order, the **c** vector is the calorific cost of each item on the menu. Our vector **b** will represent the constraints on cost, sodium, sugar and trans-fat. The matrix **A** will contain on the first row the cost of each menu item, the next row the sodium content of each menu item, the sugar content of each menu item, and finally the transfat of each item.

The code below demonstrates how you would proceed to write and then solve this program in R assuming that you have a dataframe (dt) containing the McDonalds menu items and nutritional content. (I provide a dataset and fullcode at the bottom of this article.)

1 2 3 4 5 6 7 8 9 10 |
#Setup the initial constraint problem #Most calories for <= $10 AND <= 2300mg sodium AND <= 25g sugar AND <= 20g transfat c <- df$Calories A <- matrix( c ( df$Price , df$Sodium , df$Sugar , df$TransFat ) , nrow = 4 , byrow = TRUE) dir <- c("<=","<=" , "<=","<=") b <- c(10 , 2300 , 25 , 20) types <- c(rep("I" , length(obj))) max <- TRUE sol <- Rsymphony_solve_LP(c, A, dir, b, types = types , max = max) |

You’ll also notice that a vector **dir** is created to specify an inequality for each constraint and that a **types** vector is created to specify that the values for **x** vector should be whole numbers ( because you can’t order fractional units of items at McDonalds 🙂 )

To solve this program we use the Rsymphony package – although R offers a range of packages for mathematical programming and optimisation.

(The Rsymphony package provides an interface to the Symphony solver for mixed integer linear programs. It enables the solving of large integer programs using a branch and cut algorithm written in C for speed – so it is a nice package to become familiar with.)

**Problem 2 – Late Night Drinking ‘remedy’**

It turns out that consuming protein reduces the rate of alcohol absorption so we could say: *I want to maximize my protein intake subject to total cost<= $8 AND <= 50% carbs AND <= 20% fat AND <=800 kcal*.

You may notice that the carb and fat constraints are different from example 1. In this case we want to limit the proportion of carbohydrate and fat not the total as before. This means that our constraints will need to massaged a little to fit the standard form of linear program constraints (Ax<=b) – but do not worry the massaging process is relatively trivial.

To illustrate the massaging process imagine a menu item x1 that has n grams of carbs, o grams fat, p grams protein and we want the proportion of carb to be <= q then

carb / ( carb + fat + protein ) <= q

carb <= q (carb + fat + protein)

carb – q (carb + fat + protein) <= 0

As you can see from the above we can generate an inequality constraint equivalent to Ax <= b because we can set the entry for b to zero and the entry in matrix A to a real value equal to carb – q (carb + fat + protein) – see the carb constraint in the code below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#Setup the constraint problem #Most protein for <= $8 #Ensure carbs <= 50% #Ensure fat <= 20% #Ensure calories <= 800 c <- df$Protein #carb constraint carbs <- df$Carbs b_carbs <- 0.5 carbs = carbs - (b_carbs * (df$Fat + df$Carbs + df$Protein) ) #fat constraint fat <- df$Fat b_fat <- 0.2 fat = fat - (b_fat * (df$Fat + df$Carbs + df$Protein) ) #create matrix A <- matrix( c ( df$Price , carbs , fat , df$Calories ) , nrow = 4 , byrow = TRUE) dir <- c("<=","<=" , "<=" , "<=") b <- c(8 , 0 , 0 , 800) types <- c(rep("I" , length(c))) max <- TRUE #solve sol <- Rsymphony_solve_LP(c, A, dir, b, types = types , max = max) |

If you happen to be curious about the results of each of the programs I’ve included them below. They were generated using a dataset based on the USA McDonalds Menu Prices and nutritional information.

**Problem 1 – Stuffing your face in a slightly healthier way**

1 x McChicken Carbs: 40 Protein: 14 Fat: 17 Sodium: 650 Calories 370

5 x Large French Fries Carbs: 67 Protein: 6 Fat: 24 Sodium: 290 Calories 510

Total Carbs 375 Total Protein 44 Total Fat 137 Total Sodium 2100 Total Calories 2920

**Problem 2 – Late Night Drinking ‘remedy’**

1 x Ranch Snack Wrap (Grilled) Carbs: 25 Protein: 19 Fat: 13 Sodium: 820 Calories 290

1 x Premium Bacon Ranch Salad with Grilled Chicken Carbs: 9 Protein: 38 Fat: 14 Sodium: 1120 Calories 310

1 x Fruit ‘n Yogurt Parfait Carbs: 30 Protein: 4 Fat: 2 Sodium: 80 Calories 150

Total Carbs 64 Total Protein 61 Total Fat 29 Total Sodium 2020 Total Calories 750

You can find my full code below and the dataset that it is based on here.

#Setup the environment & load the data library (Rsymphony) setwd("/Users/davidgreenwood/Dropbox/Play Projects/McMeal") df <- read.csv("McMeal.csv" , encoding = "UTF-8", header = TRUE, stringsAsFactors = FALSE) #Tidy up the data a bit colnames ( df )[4] = "Price" colnames ( df )[6] = "Weight" colnames ( df )[9] = "Fat" colnames ( df )[11] = "SaturatedFat" colnames ( df )[13] = "TransFat" colnames ( df )[16] = "Sodium" colnames ( df )[18] = "Carbs" colnames ( df )[20] = "Fiber" colnames ( df )[22] = "Sugar" colnames ( df )[23] = "Protein" filtOz <- function (x) { return (gsub("oz" , "" , x)) } filtG <- function (x) { return (gsub("\\(|\\)|g" , "" , x)) } df[,5] <- as.numeric ( vapply( df[,5] , filtOz , "character" , USE.NAMES = FALSE) ) #Filter oz col df[,6] <- as.numeric ( vapply( df[,6] , filtG , "character" , USE.NAMES = FALSE) ) #Filter gram col #Display function to see the solution displaySolution <- function ( sol ) { tFat <- 0 tCarbs <- 0 tProtein <- 0 tCalories <- 0 tSodium <- 0 for ( i in 1:length(sol) ) { if ( sol[i] > 0 ) { tFat = tFat + sol[i] * df$Fat[i] tCarbs = tCarbs + sol[i] * df$Carbs[i] tProtein = tProtein + sol[i] * df$Protein[i] tCalories = tCalories + sol[i] * df$Calories[i] tSodium = tSodium + sol[i] * df$Sodium[i] cat ( sol[i] , "x " , df[i,1] , df[i,2] , df[i,3], " Carbs:" , df$Carbs[i], " Protein:" , df$Protein[i], " Fat:" , df$Fat[i], " Sodium:" , df$Sodium[i], " Calories" , df$Calories[i], "\n" ) } } cat ( "Total Carbs " , tCarbs , "Total Protein" , tProtein , "Total Fat" , tFat , "Total Sodium" , tSodium , "Total Calories" , tCalories, "\n" ) } #Setup the initial constraint problem #Most calories for <= $10 AND <= 2300mg sodium AND <= 25g sugar AND <= 20g transfat c <- df$Calories A <- matrix( c ( df$Price , df$Sodium , df$Sugar , df$TransFat ) , nrow = 4 , byrow = TRUE) dir <- c("<=","<=" , "<=","<=") b <- c(10 , 2300 , 25 , 20) types <- c(rep("I" , length(obj))) max <- TRUE sol <- Rsymphony_solve_LP(c, A, dir, b, types = types , max = max) displaySolution ( sol$solution ) #Setup the constraint problem #Most protein for <= $10 AND <= 2300mg sodium AND <= 25g sugar AND <= 20g transfat obj <- df$Protein mat <- matrix( c ( df$Price , df$Sodium , df$Sugar , df$TransFat ) , nrow = 4 , byrow = TRUE) dir <- c("<=","<=" , "<=","<=") rhs <- c(10 , 2300 , 25 , 20) types <- c(rep("I" , length(obj))) max <- TRUE sol <- Rsymphony_solve_LP(obj, mat, dir, rhs, types = types , max = max) displaySolution ( sol$solution ) #Setup the constraint problem #Most protein for <= $8 #Ensure carbs <= 50% #Ensure fat <= 20% #Ensure calories <= 800 c <- df$Protein #carb constraint carbs <- df$Carbs b_carbs <- 0.5 carbs = carbs - (b_carbs * (df$Fat + df$Carbs + df$Protein) ) #fat constraint fat <- df$Fat b_fat <- 0.2 fat = fat - (b_fat * (df$Fat + df$Carbs + df$Protein) ) #create matrix A <- matrix( c ( df$Price , carbs , fat , df$Calories ) , nrow = 4 , byrow = TRUE) dir <- c("<=","<=" , "<=" , "<=") b <- c(8 , 0 , 0 , 800) types <- c(rep("I" , length(c))) max <- TRUE #solve sol <- Rsymphony_solve_LP(c, A, dir, b, types = types , max = max) displaySolution ( sol$solution )