Optimizing fast food orders using linear programming

What is linear programming?

Linear programming is not a concept in programming, but rather one of mathematics. Given a set of items that have associated costs and benefits, how do you find a mix of items such that the required benefits are met and the cost is minimized?

We can start off by requiring that the quantity of each item is non-negative. This greatly reduces the search space. Adding further constraints forms what is called the feasible region. Shown below, is the feasible region for a mix of two items. The set of constraints then forms the program, because it can be evaluated in order to find the solution.

Feasible region of two variables with three constraints.

So how does this help us? Since no combination of any two points in the feasible region is infeasible, this means the problem is convex. Since the problem is convex and the cost is monotonic, then the optimal solution is at one of the corner points. For the example above, the number of possible solutions has reduced from infinity to 3. From there, we can test all points on a piece of paper and pick the best choice. Luckily we have linear programming

Setup

First, we’ll need to import the pulp & pandas libraries. If you do not have them, use pip install pulp and pip install pandas.

import pulp
import pandas as pd

Now, we’ll need to download the menu data to the same directory as our code. Note: menu information may no longer be accurate, prices are regional.

Optimizing Taco Bell orders

Let’s create a model.

model = pulp.LpProblem("Fast Food Order", pulp.LpMinimize)

Before we import our menu file, let’s define some constants that will make our code more dynamic. I’m starting with Taco Bell, and specifying that the order is for one person.

restaurant = 'taco_bell'
num_people = 1

Now, we can import the menu.

foods = pd.read_csv('{0}.csv'.format(restaurant),index_col='name')

Let’s define the limit conditions for our variables. Here I’m setting a limit of one item per person to improve variety, and that the orders must be integer values.

x = pulp.LpVariable.dict('x_%s', foods.index.tolist(), lowBound=0, upBound=num_people, cat=pulp.LpInteger)

Next, we can add user preferences by specifying a must-have item. Here I have chosen the Crunchwrap Supreme, a Taco Bell classic.

x['Crunchwrap Supreme'].lowBound = 1

Now, we must specify what we’re trying to minimize. Let’s use the “price” column. A user may minimize something else instead, such as calories.

model += pulp.lpSum([foods.loc[i]['price'] * x[i] for i in foods.index.tolist()])

Let’s tell the model our nutritional requirements.

model += pulp.lpSum([foods.loc[i]['calories'] * x[i] for i in foods.index.tolist()]) >= 1320
model += pulp.lpSum([foods.loc[i]['total_fat'] * x[i] for i in foods.index.tolist()]) >= 63
model += pulp.lpSum([foods.loc[i]['protein'] * x[i] for i in foods.index.tolist()]) >= 10
model += pulp.lpSum([foods.loc[i]['sugars'] * x[i] for i in foods.index.tolist()]) <= 30
model += pulp.lpSum([foods.loc[i]['sodium'] * x[i] for i in foods.index.tolist()]) <= 100

Results

Let’s solve the model. PuLP makes this really easy.

model.solve()

Not all solutions are feasible. For example, if we require less than 10 grams of sugar, and also require an item that contains 12 grams of sugar, then there are no possible solutions. Let’s output the model status to verify that everything went smoothly.

print("nStatus: {0}".format(pulp.LpStatus[model.status]))

Now, let’s output the results.

for food in model.variables():
    if food.varValue:
        print("{0:0.0f} {1}".format(food.varValue, food.name))
print("\nPrice / person = ${0:0.2f}".format(pulp.value(model.objective) / num_people))
Status: Optimal

1 x_Beefy_Fritos_Burrito
1 x_Brisk_Unsweetened_No_Lemon_Iced_Tea_(16_fl_oz)
1 x_Crunchwrap_Supreme
1 x_Quesarito___Chicken

Price / person = $8.97

Awesome! It even includes 1 Crunchwrap Supreme, like we specified.

Optimizing McDonald’s orders

Now, let’s change the restaurant to McDonald’s.

restaurant = 'mcdonalds'

After removing our Crunchwrap Supreme item, we can re-run our code without changing anything.

Status: Infeasible

-10 x_2_Apple_Pies
1 x_Caramel_Frappe_(Small)
1 x_Chocolate_Chip_Frappe
14 x_Mocha_Frappe

Price / person = $38.34

What happened? After testing our constraints, we find that nothing is feasible unless we increase the sodium limit by 5 times, or increase the sugar limit by 3 times. Let’s increase the sugar limit to 50 grams and the sodium limit to 2000 milligrams.

Status: Optimal

1 x_3_Pack_Of_Cookies
1 x_McChicken
1 x_Sausage_Biscuit

Price / person = $4.27

Looks good.

Trying it out in real life

McDonald’s

I went to McDonald’s with 1 other person. They wanted a vanilla shake included in the order, which resulted in the following program:

2 x_McChicken
1 x_1_Cookie
1 x_Double_Hamburger
1 x_Sausage_Biscuit
1 x_Sausage_McMuffin
1 x_Vanilla_Shake

Price / person = $5.37

The actual total ended up being $2 more because they could not find the Sausage McMuffin, only a Sausage Egg McMuffin. Oh well…

Taco Bell

Due to convexity, if all you eat are Beefy Fritos Burritos, then you can eat for as little as ~$4.00. I opted for more variety by setting each item to a maximum of 1.

The result was a good variety, more than I would think to get. The variety was more complimentary to the food format than McDonald’s since it wasn’t just a bunch of random sandwiches. It ended up being ~$8 per person, which is more than the $6 at McDonald’s.

Bonus: Using optimized orders to evaluate menu items

Since we can inject the items we want into orders, we can evaluate how well each item fits as a member of an otherwise optimized meal. We can also see how adding 1 of each item affects orders for multiple people.

This results in the following table:

Item 1 2 3 4 5 6 7 8 9
3 Pack Of Cookies 4.27 4.27 4.27 4.25 4.25 4.22 4.23 4.20 4.19
McChicken 4.27 4.27 4.27 4.25 4.25 4.22 4.23 4.20 4.19
Sausage Biscuit 4.27 4.27 4.27 4.25 4.25 4.22 4.23 4.20 4.19
Sausage McMuffin 4.57 4.27 4.27 4.25 4.25 4.22 4.23 4.20 4.19
2 Apple Pies 4.57 4.42 4.37 4.29 4.29 4.22 4.23 4.23 4.19
Double Cheeseburger 5.07 4.67 4.54 4.40 4.31 4.30 4.28 4.25 4.25
Double Hamburger 5.26 4.56 4.27 4.27 4.27 4.27 4.26 4.23 4.24
Apple Slices 5.26 4.77 4.50 4.44 4.35 4.33 4.32 4.28 4.27
Strawberry Go-Gurt 5.26 4.66 4.53 4.37 4.35 4.33 4.31 4.27 4.27
Diet Coke (Small) 5.27 4.77 4.60 4.50 4.45 4.39 4.37 4.32 4.30
Diet Dr Pepper (Small) 5.27 4.77 4.60 4.50 4.45 4.39 4.37 4.32 4.30
Minute Maid Light Lemonade (Small) 5.27 4.77 4.60 4.50 4.45 4.39 4.37 4.32 4.30
Unsweetened Iced Tea 5.27 4.77 4.60 4.50 4.45 4.39 4.37 4.32 4.30
1 Cookie 5.36 4.56 4.30 4.29 4.29 4.22 4.23 4.22 4.19
Apple Pie 5.36 4.52 4.30 4.29 4.29 4.22 4.23 4.20 4.20
1% Low Fat Milk Jug 5.36 4.62 4.50 4.44 4.39 4.37 4.31 4.30 4.29
Dasani Bottled Water 5.56 4.92 4.70 4.57 4.51 4.43 4.41 4.36 4.34
Bacon McDouble 5.57 4.92 4.60 4.52 4.41 4.39 4.36 4.31 4.30
6 McNuggets 5.57 4.82 4.63 4.54 4.37 4.36 4.34 4.33 4.30
Honest Kids Organic Apple Juice Drink 5.57 4.82 4.63 4.54 4.41 4.39 4.36 4.34 4.30
MIX by Sprite Tropic Berry 5.57 4.82 4.63 4.44 4.41 4.39 4.36 4.34 4.30
Hamburger 5.66 4.67 4.46 4.34 4.33 4.22 4.23 4.23 4.24
Cheeseburger 5.66 4.66 4.47 4.25 4.25 4.25 4.26 4.25 4.22
Sausage Burrito 5.76 4.67 4.46 4.27 4.27 4.27 4.27 4.26 4.24
Hash Brown 5.76 4.87 4.63 4.47 4.43 4.37 4.34 4.33 4.27
French Fries (Small) 5.76 5.02 4.73 4.59 4.51 4.39 4.37 4.36 4.35
McDouble 6.05 4.52 4.34 4.32 4.31 4.25 4.25 4.26 4.25
Oatmeal without Brown Sugar 6.06 4.97 4.73 4.62 4.53 4.44 4.41 4.36 4.35
Triple Cheeseburger 6.16 5.17 4.87 4.64 4.49 4.45 4.41 4.38 4.36
Sausage Biscuit with Egg 6.17 5.07 4.80 4.67 4.51 4.47 4.41 4.38 4.36
4 McNuggets 6.26 5.07 4.70 4.59 4.49 4.44 4.41 4.33 4.33
Coffee (Small) 6.26 5.27 4.93 4.74 4.65 4.55 4.51 4.44 4.41
Decaf Coffee 6.26 5.27 4.93 4.74 4.65 4.55 4.51 4.44 4.41
Hot Tea 6.26 5.27 4.93 4.74 4.65 4.55 4.51 4.44 4.41
Vanilla Cone 6.27 4.67 4.53 4.42 4.37 4.27 4.27 4.27 4.27
Sausage McMuffin with Egg 6.27 5.27 4.83 4.69 4.61 4.49 4.46 4.40 4.38
Fruit & Yogurt Parfait 6.35 4.77 4.60 4.42 4.39 4.37 4.35 4.33 4.28
Fat Free Chocolate Milk Jug 6.36 4.77 4.60 4.42 4.39 4.37 4.30 4.30 4.29
Plain Sundae 6.45 4.82 4.63 4.44 4.41 4.39 4.37 4.34 4.29
2 McGriddles 6.46 4.71 4.53 4.42 4.35 4.27 4.27 4.26 4.25
Sweet Iced Tea (Small) 6.47 4.97 4.60 4.52 4.39 4.37 4.36 4.30 4.29
20 McNuggets 6.58 5.43 4.94 4.70 4.61 4.49 4.46 4.43 4.41
Iced Coffee (Small) 6.66 5.27 4.90 4.67 4.59 4.47 4.44 4.42 4.39
Iced Vanilla Coffee (Small) 6.66 5.27 4.93 4.67 4.59 4.54 4.44 4.42 4.40
Hotcakes & Sausage 6.67 5.02 4.77 4.50 4.45 4.42 4.39 4.37 4.34
Side Salad 6.76 5.37 5.00 4.82 4.65 4.58 4.54 4.46 4.44
Americano 6.86 5.57 5.13 4.89 4.77 4.65 4.60 4.52 4.48
Iced Mocha (Small) 7.06 5.47 5.07 4.82 4.69 4.62 4.50 4.47 4.45
Signature Crafted Bacon Smokehouse Artisan – Quarter 7.08 5.68 5.21 4.92 4.71 4.64 4.58 4.53 4.47
Caramel Sundae 7.17 4.87 4.53 4.32 4.31 4.30 4.30 4.28 4.26
Hot Fudge Sundae 7.17 4.87 4.57 4.40 4.31 4.30 4.30 4.30 4.26
Oatmeal 7.17 5.12 4.76 4.62 4.53 4.42 4.40 4.38 4.37
Cappuccino (Small) 7.25 5.56 5.13 4.89 4.77 4.64 4.57 4.52 4.49
Iced Latte (Small) 7.25 5.76 5.13 4.92 4.77 4.68 4.58 4.53 4.49
Latte (Small) 7.25 5.56 5.13 4.89 4.77 4.62 4.57 4.52 4.46
Big Mac 7.26 5.72 5.13 4.90 4.71 4.64 4.55 4.52 4.48
Filet-O-Fish 7.27 5.77 5.27 5.02 4.85 4.72 4.65 4.61 4.53
Iced Caramel Coffee (Small) 7.36 5.27 4.93 4.67 4.59 4.47 4.44 4.42 4.39
Iced Hazelnut Coffee (Small) 7.36 5.27 4.93 4.67 4.59 4.47 4.44 4.42 4.39
10 McNuggets 7.37 5.82 5.30 4.97 4.83 4.69 4.61 4.53 4.50
Quarter Pounder with Cheese 7.46 5.82 5.20 4.95 4.75 4.67 4.58 4.54 4.50
Coca Cola (Small) 7.66 5.02 4.67 4.50 4.45 4.40 4.34 4.33 4.30
Dr Pepper (Small) 7.66 4.87 4.67 4.50 4.45 4.35 4.34 4.30 4.29
Fanta Orange 7.66 4.92 4.67 4.50 4.45 4.35 4.34 4.32 4.30
Egg McMuffin 7.76 5.56 5.13 4.77 4.67 4.60 4.56 4.51 4.46
Double Quarter Pounder with Cheese 7.77 5.68 5.21 4.97 4.83 4.72 4.63 4.58 4.52
Buttermilk Chicken-Crispy Sandwich 7.77 6.02 5.44 5.07 4.91 4.79 4.67 4.58 4.55
Bacon Egg & Cheese Biscuit 7.86 5.47 4.97 4.80 4.63 4.57 4.47 4.45 4.43
Signature Crafted Mushroom Swiss – Crispy 7.87 5.97 5.34 4.97 4.77 4.69 4.63 4.58 4.54
Signature Crafted Mushroom Swiss – Quarter 7.87 6.07 5.34 5.04 4.89 4.74 4.63 4.58 4.55
Bacon Ranch Salad with Crispy Chicken 7.97 6.12 5.50 5.12 4.95 4.77 4.70 4.61 4.57
French Vanilla Latte (Small) 8.06 5.67 5.07 4.79 4.69 4.62 4.57 4.52 4.45
Southwest Salad with Crispy Chicken 8.06 6.12 5.50 5.12 4.93 4.77 4.68 4.62 4.57
Sprite 8.16 5.27 4.67 4.50 4.45 4.42 4.34 4.30 4.29
Deluxe Quarter Cheese 8.17 6.02 5.43 5.02 4.87 4.72 4.61 4.57 4.54
Bacon Big Mac 8.17 6.02 5.44 5.02 4.87 4.77 4.61 4.57 4.54
Signature Crafted Double Mushroom Swiss – Quarter 8.17 6.02 5.44 5.12 4.89 4.79 4.68 4.62 4.58
Signature Crafted Double Bacon Smokehouse Quarter 8.18 5.78 5.27 4.93 4.79 4.66 4.60 4.56 4.49
Sausage McGriddles 8.25 5.27 4.94 4.72 4.55 4.50 4.47 4.43 4.41
Iced Vanilla Latte (Small) 8.25 5.52 5.10 4.89 4.69 4.62 4.57 4.52 4.49
4 Piece Buttermilk Crispy Chicken Tenders 8.26 5.52 5.10 4.82 4.71 4.57 4.53 4.46 4.44
Bacon Ranch Salad 8.26 6.11 5.37 5.09 4.89 4.78 4.70 4.58 4.55
Southwest Salad 8.26 6.11 5.47 5.09 4.93 4.78 4.71 4.64 4.55
Double Filet-O-Fish 8.37 6.17 5.53 5.12 4.95 4.84 4.71 4.66 4.60
Strawberry Sundae 8.46 4.92 4.63 4.47 4.43 4.30 4.30 4.30 4.29
Caramel Macchiato 8.55 5.37 5.00 4.82 4.67 4.60 4.53 4.45 4.43
Iced Caramel Latte (Small) 8.55 5.52 5.10 4.89 4.69 4.62 4.57 4.52 4.49
Iced Hazelnut Latte (Small) 8.55 5.52 5.10 4.89 4.69 4.62 4.57 4.52 4.49
Minute Maid Orange Juice 8.75 5.57 5.03 4.77 4.67 4.59 4.50 4.47 4.45
Caramel Latte (Small) 8.75 5.67 5.07 4.87 4.71 4.62 4.56 4.47 4.45
Hazelnut Latte (Small) 8.75 5.67 5.07 4.87 4.71 4.62 4.56 4.47 4.45
Vanilla Cappuccino 8.75 5.67 5.10 4.89 4.69 4.62 4.57 4.52 4.49
Sausage Egg & Cheese McGriddles 8.85 5.47 4.93 4.75 4.65 4.52 4.48 4.46 4.39
Hotcakes Only 8.86 5.22 4.80 4.65 4.51 4.47 4.41 4.39 4.37
Iced Caramel Macchiato (Small) 8.86 5.57 5.13 4.74 4.65 4.59 4.54 4.49 4.43
Deluxe Double Quarter Cheese 9.37 6.62 5.83 5.32 5.11 4.92 4.79 4.72 4.67
Premium Hot Chocolate (Small) 9.76 5.51 4.93 4.67 4.53 4.49 4.46 4.43 4.38
Mocha (Small) 9.86 5.61 5.10 4.84 4.65 4.54 4.50 4.47 4.45
Strawberry Banana Smoothie 9.95 6.02 5.33 5.07 4.83 4.74 4.64 4.59 4.55
Mango-Pineapple Smoothie (Small) 9.95 6.02 5.43 5.04 4.83 4.74 4.64 4.59 4.55
Caramel Cappuccino (Small) 10.06 5.67 5.20 4.87 4.75 4.62 4.57 4.52 4.45
Hazelnut Cappuccino (Small) 10.06 5.67 5.20 4.87 4.75 4.62 4.57 4.52 4.45
Bacon Quarter Pounder with Cheese 10.65 6.32 5.50 5.20 4.97 4.80 4.73 4.60 4.56
Bacon Ranch Salad with Grilled Chicken 10.95 6.56 5.77 5.39 5.01 4.89 4.80 4.73 4.65
Signature Crafted Mushroom Swiss – Grilled 11.26 6.27 5.50 5.17 4.99 4.87 4.73 4.66 4.61
Grilled Chicken Southwest Salad 12.06 6.56 5.77 5.27 5.03 4.89 4.80 4.69 4.65
M&M McFlurry 6.07 4.74 4.54 4.49 4.44 4.37 4.36 4.32
Oreo McFlurry 5.42 4.80 4.62 4.51 4.47 4.38 4.37 4.36
Chocolate Shake (Small) 5.87 4.84 4.70 4.59 4.50 4.47 4.41 4.38
Vanilla Shake 5.37 4.90 4.74 4.57 4.47 4.44 4.41 4.39
Strawberry Shake (Small) 5.81 5.03 4.70 4.61 4.52 4.47 4.41 4.39
Caramel Frappe (Small) 5.62 5.04 4.85 4.69 4.62 4.57 4.48 4.46
Chocolate Chip Frappe 5.62 5.04 4.85 4.69 4.62 4.56 4.48 4.46
Mocha Frappe 5.62 5.04 4.85 4.69 4.62 4.56 4.48 4.46
Signature Crafted Bacon Smokehouse Artisan – Crispy 5.68 5.11 4.82 4.69 4.62 4.57 4.48 4.45
Bacon Egg & Cheese McGriddles 5.72 5.24 4.87 4.75 4.65 4.55 4.51 4.48
6 Piece Buttermilk Crispy Chicken Tenders 6.07 5.44 5.12 4.89 4.74 4.67 4.62 4.55
Signature Crafted Bacon Smokehouse Artisan – Grilled 6.42 5.47 4.97 4.83 4.74 4.64 4.55 4.51
Grilled Artisan Chicken Sandwich 6.46 5.54 5.22 4.99 4.85 4.73 4.67 4.61
10 Piece Buttermilk Crispy Chicken Tenders 6.41 5.75 5.41 5.14 5.02 4.90 4.82

Interesting. We also note that some items are infeasible, probably because they exceed limits on their own. There is also a dilution effect as you add more people to the order.

Full code

import pulp
import pandas as pd

model = pulp.LpProblem("Fast Food Meal", pulp.LpMinimize)

restaurant = 'taco_bell'
num_people = 1

foods = pd.read_csv('{0}.csv'.format(restaurant),index_col='name')

# Variables
x = pulp.LpVariable.dict('x_%s', foods.index.tolist(), lowBound=0, upBound=num_people, cat=pulp.LpInteger)

# Fixed items
x['Crunchwrap Supreme'].lowBound = 1

# Objective function based on cost of the foods
model += pulp.lpSum([foods.loc[i]['price'] * x[i] for i in foods.index.tolist()])

# Dietary Constraints
model += pulp.lpSum([foods.loc[i]['calories'] * x[i] for i in foods.index.tolist()]) >= 1320 * num_people
model += pulp.lpSum([foods.loc[i]['total_fat'] * x[i] for i in foods.index.tolist()]) >= 63 * num_people
model += pulp.lpSum([foods.loc[i]['protein'] * x[i] for i in foods.index.tolist()]) >= 10 * num_people
model += pulp.lpSum([foods.loc[i]['sugars'] * x[i] for i in foods.index.tolist()]) <= 50 * num_people
model += pulp.lpSum([foods.loc[i]['sodium'] * x[i] for i in foods.index.tolist()]) <= 2000 * num_people

model.solve()

print("\nStatus: {0}\n".format(pulp.LpStatus[model.status]))

for food in model.variables():
    if food.varValue:
        print("{0:0.0f} {1}".format(food.varValue, food.name))
print("\nPrice / person = ${0:0.2f}".format(pulp.value(model.objective) / num_people))

About the author



Hi, I'm Nathan. I'm an electrical engineer in the Los Angeles area. Keep an eye out for more content being posted soon.


Leave a Reply

Your email address will not be published. Required fields are marked *