Shopping for Bananas: An Optimized approach

The other day I went to buy bananas with 28 Banana Money in my hand. My end goal was well defined. 'Buy as many bananas as possible with the money I had'. The only problem was, there were many banana vendors, each quoting their own prices and their own discount policy.

This brought me to a thought: If I have the necessary tools with me, will I be able to purchase bananas in the most optimal way.

The Optimized banana purchase:

To simplify the problem, lets just assume there were only three vendors, and these vendors had 10 bananas each. All the vendors sold at different base prices and offered different discount schemes.

Vendor A: Base Price of 9 Banana Money, 8% reduction in the cost
Vendor B: Base Price of 7 Banana Money, 4% reduction in the cost
Vendor C: Base Price of 8 Banana Money, 7% reduction in the cost

The X-axis denotes the number of bananas purchased from a Vendor, and the Y-axis denotes the Price in Banana Money for the total purchase.

# of Banans	Price (Banana Money)
	Vendor A Price per banana	Vendor A Total Price	Vendor B Price per banana	Vendor B Total Price	Vendor C Price per Banana	Vendor C Total Price
1	9.00	9.00	7.00	7.00	8.00	8.00
2	8.28	16.56	6.72	13.44	7.44	14.88
3	7.62	22.85	6.45	19.35	6.92	20.76
4	7.01	28.03	6.19	24.77	6.43	25.74
5	6.45	32.24	5.95	29.73	5.98	29.92
6	5.93	35.59	5.71	34.25	5.57	33.39
7	5.46	38.20	5.48	38.36	5.18	36.23
8	5.02	40.16	5.26	42.08	4.81	38.51
9	4.62	41.57	5.05	45.45	4.48	40.29
10	4.25	42.49	4.85	48.48	4.16	41.63

Modelling the problem:

Maximize:
   n, where n is the number of bananas
Constrained to:
   ∑c_i <= 28, where c_i is the cost of the i bananas bought.
   ∑i = n 

This problem statement is a special class of linear programming model known as Special ordered Sets (SOS). To correlate how our problem fits into the SOS domain, specifically SOS-1 lets look at the actors in this optimization problem:

Bananas: Each banana purchased from a vendor quotes a different price, also, they can just be bought in discrete numbers ie.  4.5 bananas are not sold. 

The number of bananas in this model would become the special ordered set and and can be modelled using a binary/boolean array. The truth value of the array would specify how many bananas have been picked up from each vendor.

Modelling Using Python, PuLP:

We start by defining the problem:

banana_shopping = pulp.LpProblem('Banana Shopping', pulp.LpMaximize)

The banana shopping problem is a maximization problem as we are trying to maximize the number of bananas purchased. 

Defining bananas: As mentioned earlier, the bananas form SOS-1 variables in the given problem statement. The bananas are defined as 'The number of bananas purchased from each vendor', which will range from 0 to total number of bananas per vendor.

bananas = [range(total_bananas_per_vendor + 1) for i in range(total_vendors)]

selected_bananas = [
  [pulp.LpVariable('vendor_' + str(i) + '_' + str(j) + '_bananas', cat='Binary') 

  for j in range(total_bananas_per_vendor + 1)]
  for i in range(1, total_vendors + 1)
  ]

for i in range(total_vendors):
  banana_shopping += pulp.lpSum(
    [selected_bananas[i][j] for j in range(total_bananas_per_vendor + 1)]
  ) == 1, 'SOS constraint ' + str(i)

The SOS constraint makes sure that only one 'count' of bananas are chosen from a specific vendor.

Constraining Total number of Bananas in the Universe: We will have to tell the optimizer that there are only finite number of bananas with the vendors.

total_bananas = flatten(
  [[selected_bananas[i][j] * bananas[i][j] for j in range(total_bananas_per_vendor + 1)]
   for i in range(total_vendors)]
)

banana_shopping += pulp.lpSum(total_bananas) <= total_vendors * total_bananas_per_vendor, 'Total available bananas'

Constraining the price: Once we established how many bananas we have in the universe, we now constrain the price. The total cost cannot go beyond the Banana Money available.

target_banana_money = flatten(
  [[selected_bananas[i][j] * banana_price[i][j] * bananas[i][j] for j in range(total_bananas_per_vendor + 1)]
   for i in range(total_vendors)]
)

banana_shopping += pulp.lpSum(target_banana_money) <= banana_money, 'Available Banana Money'

Defining the Objective: The Objective can be defined as 'Maximize the number of Bananas'

banana_shopping += pulp.lpSum(total_bananas), 'Objective'

We would be reusing the same definition of total_bananas.

The Optimal Number of bananas: Now to figure out how many bananas I can optimally buy for 28 Banana Money:

Vendor:1, Bananas: 0
Vendor:2, Bananas: 3
Vendor:3, Bananas: 1

The Complete code with other examples around Linear optimization with PuLP can be found here

The real world banana purchase

The purchase din't go as well as I had planned, The vendors were street smart and I was not, so I ended up walking home with a bad deal.