Pizza Problem

Ordering a pizza would be a trivial task if it weren’t for the option of choosing two flavors. In this text we will explain how this freedom given to the customer turns the “simple” action of ordering a pizza into a serious optimization problem.

First, let’s define this flavor option as follows: for each pizza we can choose up to two flavors {x; y} so that the total value of the pizza will be Max {price (x); price (y)}. To simplify communication, we will work with imaginary “zero-coin” money or just Z $. Thus, the challenge arises for the client to find flavors {x; y} such that it minimizes the function |price(x) – price(y)|/2 (since the most expensive half of the pizza was properly paid for its correct value). For example, take the following list of pizzas:

1) pepperoni, mozzarella, onion, fried garlic / 20Z $ 2) pepperoni, mozzarella, onion, fried garlic, cheddar, bacon / 25Z $ 3) tuna, mozzarella, onion, fried garlic, cheddar / 25Z $ 4) chicken, mozzarella, onion, fried garlic, cheddar / 24Z $ 5) chicken, mozzarella, onion, fried garlic, cheddar, bacon / 26Z $ 6) tuna, mozzarella, onion, fried garlic / 22Z $ 7) broccoli, mozzarella, onion, fried garlic, cheddar / 26Z $ 8) pepperoni, mozzarella, onion, fried garlic, cheddar / 23Z $ 9) tuna, mozzarella, onion, fried garlic, cheddar, bacon / 27Z $ 10) broccoli, mozzarella, onion, fried garlic / 23Z $ 11) broccoli, mozzarella, onion, fried garlic, cheddar, bacon / 28Z $ 12) chicken, mozzarella, onion, fried garlic / 21Z $

We can simplify this menu by organizing it based on common factors, as for example all pizzas come with mozzarella, onion and fried garlic, we can omit this information in the analysis. We will distribute them in two subgroups, as the main ingredient and price. To facilitate our analysis, let’s consider that adding ingredients always makes the pizza better. Thus, a pepperoni+cheddar+bacon pizza will be better than a pepperoni+cheddar pizza, which will be better than a pepperoni pizza.

Distribution by flavor: 1) pepperoni / 20Z $ 8) pepperoni, cheddar / 23Z $ 2) pepperoni, cheddar, bacon / $ 25Z 12) chicken / $ 21Z 4) chicken, cheddar / 24Z $ 5) chicken, cheddar, bacon / 26Z $ 6) Tuna / $ 22Z 3) tuna, cheddar / 25Z $ 9) tuna, cheddar, bacon / 27Z $ 10) broccoli / 23Z $ 7) broccoli, cheddar / 26Z $ 11) broccoli, cheddar, bacon / 28Z $

Price distribution: 1) pepperoni / 20Z $ 12) chicken / $ 21Z 6) Tuna / $ 22Z 10) broccoli / 23Z $ 8) pepperoni, cheddar / 23Z $ 4) chicken, cheddar / 24Z $ 2) pepperoni, cheddar, bacon / $ 25Z 3) tuna, cheddar / 25Z $ 5) chicken, cheddar, bacon / 26Z $ 7) broccoli, cheddar / 26Z $ 9) tuna, cheddar, bacon / 27Z $ 11) broccoli, cheddar, bacon / 28Z $

So, based on the quality criterion, if we will order for example half the pizza of flavor5 (chicken, cheddar, bacon) and we want the other half with pepperoni based ingredient, we have the following situations:

Max {price (flavor5); price (flavor1)} =

= Max {26Z $; 20Z $} = 26Z $.

Max {price (flavor5); price (flavor8)} =

= Max {26Z $; 23Z $} = 26Z $.

Max {price (flavor5); price (flavor2)} =

= Max {26Z $; 25Z $} = 26Z $.

Analyzing the function |price(x) – price(y)| to be minimized for each case, we have:

|price(flavor5) – price(flavor1)|/2 = 3Z$.

|price(flavor5) – price(flavor8)|/2 = 1,5Z$.

|price(flavor5) – price(flavor2)|/2 = 0,5Z$.

Therefore, flavor2 minimizes the cost in this case. On the other hand, if only the flavor5 was defined, that is, the other half of the pizza had no flavor restriction, we would have a better solution when choosing the flavor7.

Max {price (flavor5); price (flavor7)} =

= Max {26Z$; 26Z$} = 26Z$.

|price (flavor5) – price (flavor7)| = 0Z$.

Now if two pizzas are ordered, we have the possibility to choose up to 4 flavors. Its cost will be given by the expression:

[Max {price (x); price (y)} + Max {price (w); price (z)}].

Thus, the challenge arises for the client to find flavors {x; y; w; z} and rearrange them in a way that minimizes the function [|price(x) – price(y)| + |price(w) – price(z)|]/2. In this case, we have in addition to the problem of choosing, the problem of rearranging. Because 4 flavors (called 1, 2, 3 and 4) could be arranged in 3 ways:

{1; 2} & {3; 4} // {1; 3} & {2; 4} // {1; 4} & {2; 3}

Considering the same menu used in the case of just one pizza, suppose that customers want a main flavor of each type (pepperoni, chicken, tuna and broccoli), respectively, and do not insist on extras (but if possible, they want). Then we have flavor1 (pepperoni/20Z$), flavor12 (chicken/21Z$), flavor6 (tuna/22Z$) and flavor10 (broccoli/23Z$).

{flavor1; flavor12} & {flavor6; flavor10} = total to pay 44Z$

{flavor1; flavor6} & {flavor12; flavor10} = total to pay 45Z$

{flavor1; flavor10} & {flavor6; flavor12} = total to pay 45Z$

Now calculating the differences for each option, we have:

[|price(flavor1) – price(flavor12)|

+ |price(flavor6) – price(flavor10)|]/2 = 1Z$.

[|price(flavor1) – price(flavor6)|

+ |price(flavor12) – price(flavor10)|]/2 = 2Z$.

[|price(flavor1) – price(flavor10)|

+ |price(flavor6) – price (flavor12)|]/2 = 2Z$.

The first option may seem the most interesting, but the third option allows us to improve the pepperoni pizza, asking for the flavor8 (pepperoni, cheddar) instead.

{flavor8; flavor10} & {flavor6; flavor12} = total to pay 45Z$

[|price(flavor8) –price(flavor10)|

+ |price(flavor6) – price(flavor12)|]/2 = 0,5Z$.

So, if we think about which option we will spend less, in the first option we spend 44Z $, however the waste (the extra amount paid for the pizza) is 1Z $. Whereas in the fourth option we spend 45Z $, but the waste in this case is 0,5Z $.