Maximize the Taste of Your Pizza

Author(s): Optimization team

Originally published on Towards AI.

Many individuals have a fondness for pizza, with preferences ranging from spicy and vegan to vegetarian, pescetarian, carnivoran, machiavellian, or simply the classic cheese lovers.

Consider the challenge faced by the Pizzeria owner, attempting to navigate the intricacies of running a business while catering to the diverse tastes of their customers. To address this dilemma, they wisely brought in a data scientist (DS) with expertise in SQL. Fortunately, the DS shared a deep love for pizza, as per the job description.

The DS’s task was to devise a solution, and here’s what they came up with: The graph below illustrates the preferences of 50 customers regarding 20 different pizza ingredients. The data has been anonymized to safeguard the Pizzeria from potential GDPR-related legal issues, ensuring that customer preferences for pineapple or garlic in pizza remain confidential.

Take, for example, Customer 0, who favors Pepperoni, Pineapple, and garlic while expressing a distaste for Ricotta cheese, Bacon, and onion. This valued customer remains indifferent to the other ingredients. Therefore, as long as the menu incorporates the preferred elements (in green) and excludes the disliked ones (in red), satisfaction is maintained.

With the customers’ preferences now known to the data scientist (DS), the next step involves determining how to formulate the problem mathematically. This phase stands as the pivotal component in decision-making.

Objective: Maximize customer satisfaction by optimizing the number of delighted customers.

Constraints: Ensure compliance with all requirements, recognizing that handling a challenging customer is akin to dealing with a bitter fruit — demanding sweetness while potentially leaving a sour taste.

Variables: Employ binary variables to indicate the selection of ingredients (Xe) and satisfied customers (Uc).

{(0, 'L'): {2, 10, 13, 18},
 (0, 'D'): {5, 8, 16},
 (1, 'L'): set(),
 (1, 'D'): set(),
 (2, 'L'): set(),
 (2, 'D'): {0, 2, 4, 18},
 (3, 'L'): {12, 13, 14},
 (3, 'D'): set(),
 (4, 'L'): {15},
 (4, 'D'): {4, 5, 6, 18},
 (5, 'L'): {0, 8},
 (5, 'D'): {6},
 (6, 'L'): {0, 13, 14, 17},
 (6, 'D'): {4, 7, 10},
 (7, 'L'): {1, 6, 10, 14},
 (7, 'D'): {15},
 (8, 'L'): {3, 7, 18},
 (8, 'D'): {4, 5, 9, 15},
 (9, 'L'): {10, 15},
 (9, 'D'): {8, 14, 18, 19},
 (10, 'L'): set(),
 (10, 'D'): {7, 14, 16},
 (11, 'L'): {1, 2, 12},
 (11, 'D'): {3, 10},
 (12, 'L'): {5, 10, 13},
 (12, 'D'): {19},
 (13, 'L'): {1, 8, 14, 16},
 (13, 'D'): {4, 12},
 (14, 'L'): {0, 10, 12},
 (14, 'D'): set(),
 (15, 'L'): {4},
 (15, 'D'): {11},
 (16, 'L'): set(),
 (16, 'D'): {3, 8, 10, 17},
 (17, 'L'): {0, 11, 17, 18},
 (17, 'D'): {6, 19},
 (18, 'L'): {17},
 (18, 'D'): {9, 11, 19},
 (19, 'L'): {4, 7, 11},
 (19, 'D'): set(),
 (20, 'L'): {5, 8, 15, 16},
 (20, 'D'): {2, 11},
 (21, 'L'): set(),
 (21, 'D'): {0, 6, 10, 13},
 (22, 'L'): {2, 5, 7, 17},
 (22, 'D'): {1, 3, 18},
 (23, 'L'): {3, 13},
 (23, 'D'): {4, 8, 12},
 (24, 'L'): {8},
 (24, 'D'): {3, 5, 17, 19},
 (25, 'L'): {0, 7, 9, 10},
 (25, 'D'): {2, 6, 19},
 (26, 'L'): {10, 18},
 (26, 'D'): {3, 4, 7},
 (27, 'L'): {3, 6},
 (27, 'D'): {7, 9, 16},
 (28, 'L'): {7, 17},
 (28, 'D'): set(),
 (29, 'L'): set(),
 (29, 'D'): {4, 6},
 (30, 'L'): set(),
 (30, 'D'): {0, 4, 5, 19},
 (31, 'L'): {5, 8, 18},
 (31, 'D'): {0, 12, 13},
 (32, 'L'): {8},
 (32, 'D'): {0, 7},
 (33, 'L'): set(),
 (33, 'D'): {0, 2, 12},
 (34, 'L'): set(),
 (34, 'D'): {3, 15},
 (35, 'L'): set(),
 (35, 'D'): set(),
 (36, 'L'): {7},
 (36, 'D'): {0, 19},
 (37, 'L'): {6},
 (37, 'D'): {5, 13, 15, 19},
 (38, 'L'): {7, 9, 16, 18},
 (38, 'D'): {3},
 (39, 'L'): {10, 13, 17},
 (39, 'D'): {15},
 (40, 'L'): {9, 15},
 (40, 'D'): {8, 10, 18, 19},
 (41, 'L'): {0, 5},
 (41, 'D'): {14, 16},
 (42, 'L'): {4, 13},
 (42, 'D'): set(),
 (43, 'L'): {4, 8, 16},
 (43, 'D'): {6, 7, 10},
 (44, 'L'): {0, 12},
 (44, 'D'): {3, 5, 8, 9},
 (45, 'L'): {2, 10},
 (45, 'D'): set(),
 (46, 'L'): {2, 5, 9, 12},
 (46, 'D'): set(),
 (47, 'L'): set(),
 (47, 'D'): set(),
 (48, 'L'): {4, 7, 13},
 (48, 'D'): {1},
 (49, 'L'): {0, 15},
 (49, 'D'): {2, 4, 12, 13}}

Python code

import networkx as nx
import matplotlib.pyplot as plt

pizza_ingredients = [
 'Mozzarella cheese',
 'Tomato sauce',
 'Pepperoni',
 'Mushrooms',
 'Green peppers',
 'Onions',
 'Black olives',
 'Sausage',
 'Bacon',
 'Ham',
 'Pineapple',
 'Jalapeños',
 'Fresh basil',
 'Garlic',
 'Olive oil',
 'Parmesan cheese',
 'Ricotta cheese',
 'Spinach',
 'Cherry tomatoes',
 'Anchovies'
]


plt.figure(figsize=(12,6))
for c in customers:
 X= [c for e in elements]
 Y= [e for e in elements]
 plt.scatter(X,Y, c='grey', s=20, alpha=0.4) 

 
 x= [c for e in data[c,'L'] ]
 y= [e for e in data[c,'L'] ]
 plt.scatter(x,y, c='g', s=50)
 x= [c for e in data[c,'D'] ]
 y= [e for e in data[c,'D'] ]
 plt.scatter(x,y, c='r', s=50)
 
plt.xticks(list(customers),rotation=90, fontweight='bold')
plt.yticks(list(elements), pizza_ingredients, fontweight='bold')

plt.ylabel(' Ingredients ', fontweight='bold')
plt.xlabel(' Customers ', fontweight='bold')
plt.tight_layout()

fname = 'base_pizza.png'
plt.savefig(fname)

# Download the file
files.download(fname)
plt.show()

%pip install ortools
from ortools.sat.python import cp_model

def main():
 model = cp_model.CpModel()

 X = {e:model.NewBoolVar(f"x_{e}") for e in elements}
 Sc = {c:model.NewBoolVar(f"S_{c}") for c in customers}

 for c,v in Sc.items():
 for e in data[c,'L']:
 model.Add(v<= X[e])
 for e in data[c,'D']:
 model.Add(v<= 1-X[e])
 
 expressions = [v for s,v in Sc.items() ]
 model.Maximize( cp_model.LinearExpr.Sum(expressions))

 solver = cp_model.CpSolver()
 status = solver.Solve(model)

Simulation results:

The selected ingredients, including HAM, are denoted by the horizontal lines, while satisfied customers are represented by the vertical golden lines. For example, customer 1, an easy customer, has no specific preferences or dislikes, while customer 28 has two preferred ingredients (in green) and no disliked ingredients (in red).

The total value of the overall objective function is 17. If you’re interested in the Python code, it can be located in the GitHub repository. Please find it in the comment section, as LinkedIn restricts posts with links. All links are equal, but some are more equal.

Completely ignoring the disliked ingredients:

If the dislike of ingredients is ignored and limit the number of allowed ingredients to 10, then the results will be as follows:

28 satisfied customers.

Tolerate up to one dislike ingredients:

limit the number of allowed ingredients to 10, then the results will be as follows:

21 satisfied customers.

Tolerate if liked ones are more than disliked ingredients:

limit the number of allowed ingredients to 10, then the results will be as follows:

27 satisfied customers.

I understand this is a simplified scenario, and in real-world pizzerias, numerous other considerations and constraints come into play, so sit back, relax, and enjoy your pizza.

This problem was inspired by the google-hash-code-2022-practice-problem.

Github: https://github.com/OptimizationExpert/Pyomo

Enjoy!

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI