What is linear programming?

Linear programming is a powerful mathematical tool to optimize the mix of items in a set with associated costs and benefits.

Constraints are used to form the feasible region, and the optimal solution is found at one of the corner points. This method is helpful in various fields, including Fast Food Order optimization.

This tutorial will show you how to use linear programming to optimize fast food orders for cost-effectiveness.

Setup

The first step in using linear programming to optimize fast food orders is setting up the necessary libraries and data.

To begin, we’ll need to import the pulp and pandas libraries. These libraries provide the tools we need to create and solve linear programming models. If you don’t have these libraries installed, you can easily install them by running the commands “pip install pulp” and “pip install pandas” in your command line.

import pulp
import pandas as pd

Once you have the libraries installed, we’ll need to download the menu data to the same directory as your code. It’s important to note that menu information may not always be accurate, as prices can vary by region.

Optimizing Taco Bell orders

In this example, we’ll use Taco Bell as the fast food chain and create a model for one person.

The first step is to create a new linear programming model using the pulp library. This is done by defining a new LpProblem object and specifying that we want to minimize the cost of the order.

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

Next, we’ll define some constants that will make the code more dynamic. In this case, we’re specifying that we’re ordering from Taco Bell and that the order is for one person.

restaurant = 'taco_bell'
num_people = 1

We can then import the menu data stored in a CSV file in the same directory as our code. The menu data contains information about the available items, such as their cost and nutritional information.

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

We can then define the limit conditions for our variables. In this case, we’re setting a limit of one item per person to improve the variety, and the orders must be integer values.

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

To add user preferences, we can specify a must-have item. In this example, we’ve chosen the Crunchwrap Supreme, a Taco Bell classic.

x['Crunchwrap Supreme'].lowBound = 1

We must then specify what we’re trying to minimize. In this case, we use the “price” column to minimize the order cost. However, a user may choose to minimize something else, such as calories.

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

Finally, we’ll specify the nutritional requirements for the order. In this example, we’re setting requirements for calories, total fat, protein, sugars, and sodium.

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

Once all the constraints and objectives have been defined, the model can be solved to find the optimal combination of items that meet the specified requirements and minimize the order cost.

Results

Once the model has been defined, and all the necessary constraints and objectives have been set, it’s time to solve the model to find the optimal solution. The pulp library makes this easy with the built-in “solve()” function.

model.solve()

It’s important to note that not all solutions are feasible. For example, if the requirement is less than 10 grams of sugar, and an item contains 12 grams of sugar, then there are no possible solutions. Therefore, it’s a good idea to check the model status after solving to ensure everything goes smoothly.

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

Once the model has been solved, you can output the results. This can be done by iterating through the model’s variables and printing their values. The solution will show you the optimal combination of items that meet the specified requirements and minimize the cost of the order.

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))

In this example, the output shows that the optimal solution includes 1 Beefy Fritos Burrito, 1 Brisk Unsweetened No Lemon Iced Tea (16 fl oz), 1 Crunchwrap Supreme, and 1 Quesarito – Chicken. The total cost of the order is $8.97 per person.

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

As we can see, the example shows how the model includes 1 Crunchwrap Supreme, which is the must-have item that we specified.

Optimizing McDonald’s orders

In this section, we’ll show you how to use linear programming to optimize fast food orders from McDonald’s.

restaurant = 'mcdonalds'

We’ll remove the Crunchwrap Supreme item and re-run the code. The results show that the model is infeasible unless we increase the sodium limit by five times or increase the sugar limit by three times.

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

To make the solution feasible, we’ll 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

The solution is now feasible.

Trying it out in real life

The previous sections show how to use linear programming to find the best combination of items, but how does this approach work in real life?

McDonald’s

I went to McDonald’s with one other person to test it out. 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 total was $2 more because they could not find the Sausage McMuffin, only a Sausage Egg McMuffin. Oh well…

Taco Bell

I also tried this approach at Taco Bell. Due to the convexity of the problem, if all you eat are Beefy Fritos Burritos, you can eat them 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 of items that were more complimentary to the food format than McDonald’s, and it ended up being ~$8 per person, which is more than the $6 at McDonald’s.

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))