Python PuLP Optimization Problem - Minimize Deviation from Average

Question

I am trying to do an Optimization problem with PuLP but I am having an issue with writing my objective function.

I've simplified my real-life example to a simpler one using cereal. So let's say I have a list of products and a number of Aisles I can put them into (for this example 2). Each product has a number we normally sell each week (ex: we sell 20 boxes of Fruit Loops and 6 boxes of Cheerios each week). Each item also needs a certain amount of shelves (ex: Frosted Flakes needs 1 shelf, but Corn Flakes needs 2).

Product	Sales	Shelves	Assigned Aisle
Fruit Loops	20	2
Frosted Flakes	15	1
Cocoa Pebbles	8	1
Fruitty Pebbles	9	1
Corn Flakes	12	2
Cheerios	6	1

Each aisle only has 4 shelves. So in theory I could put Fruit Loops and Corn Flakes together in one Aisle (2 shelves + 2 shelves). If I put those in an Aisle the weekly sales from that Aisle would be 20 + 12 = 32. If I put the other 4 items (1 shelf + 1 + 1 + 1) in an Aisle then that Aisles sales would be 15 + 8 + 9 + 6 = 38. The average sales in an Aisle should be 35. The goal of my optimization problem is for each Aisle to be as close to that Average number as possible. I want to minimize the total absolute difference between each Aisles Total Weekly Sales and the Average number. In this example my deviation would be ABS(38-35) + ABS(32-35) = 6. And this is the number I want to minimize.

I cannot figure out the way to write that so PuLP accepts my objective. I can't find an example online with that level of complexity where it's comparing each value to an average and taking the cumulative absolute deviation. And when I write out code that technically would calculate that PuLP doesn't seem to accept it.

Here's some example code:

products = ['Fruit Loops', 'Frosted Flakes', 'Cocoa Pebbles', 'Fruitty Pebbles', 'Corn Flakes', 'Cheerios']

sales = {'Fruit Loops': 20, 'Frosted Flakes': 15, 'Cocoa Pebbles': 8, 'Fruitty Pebbles': 9, 'Corn Flakes': 12, 'Cheerios': 6}

shelves = {'Fruit Loops': 2, 'Frosted Flakes': 1, 'Cocoa Pebbles': 1, 'Fruitty Pebbles': 1, 'Corn Flakes': 2, 'Cheerios': 1}

from pulp import *

problem = LpProblem('AisleOptimization', LpMinimize)

# For this simplified example there are only 2 aisles
Num_of_Aisles = 2

# Each Aisle has 4 shelves and can't have more than 4 shelves filled
Max_Shelves_Aisle = 4

# The Optimizer can change the Aisle each Product is assigned to try and solve the problem
AislePick = LpVariable.dicts('AislePick', products, lowBound = 0, upBound = (Num_of_Aisles - 1), cat='Integer')

# My attempt at the Minimization Formula
# First Calculate what the average sales would be if split perfectly between aisles
avgsales = sum(sales.values()) / Num_of_Aisles

# Loop through and calculate total sales in each aisle and then subtract from the average
problem += lpSum([sum(v for _, v in value) - avgsales for _, value in itertools.groupby(sorted([(aisle, sales[product]) for product, aisle in AislePick.items()]), lambda x: x[0])]), 'Hits Diff'

# Restriction so each Aisle can only have 4 shelves
for aisle in range(Num_of_Aisles):
    problem += lpSum([shelves[prod] for prod, ais in AislePick.items() if ais == aisle]) <= Max_Shelves_Aisle, f"Sum_of_Slots_in_Aislel{aisle}"

problem.solve()

The result I get is -3

If I run LpStatus[problem.status] I get Undefined. I assume my is that my objective function is too complex, but I'm not sure.

Any help is appreciated.

Answer 1

Your main issue here is that the ABS function is non-linear. (So is whatever sorting thing you were trying to do... ;) ). So you have to reformulate. The typical way to do this is to introduce a helper variable and consider the "positive" and "negative" deviations separately from the ABS function as both of those are linear. There are several examples of this on the site, including this one that I answered a while back:

How to make integer optimization with absolute values in python?

That introduces the need bring the aisle selection into the index, because you will need to have an index for the aisle sums or diffs. That is not too hard.

Then you have to (as I show below) put in constraints to constrain the new aisle_diff variable to be larger than both the positive or negative deviation from the ABS.

So, I think the below works fine. Note that I introduced a 3rd aisle to make it more interesting/testable. And I left a few comments on your now dead code.

from pulp import *

products = ['Fruit Loops', 'Frosted Flakes', 'Cocoa Pebbles', 'Fruitty Pebbles', 'Corn Flakes', 'Cheerios']
sales = {'Fruit Loops': 20, 'Frosted Flakes': 15, 'Cocoa Pebbles': 8, 'Fruitty Pebbles': 9, 'Corn Flakes': 12, 'Cheerios': 6}
shelves = {'Fruit Loops': 2, 'Frosted Flakes': 1, 'Cocoa Pebbles': 1, 'Fruitty Pebbles': 1, 'Corn Flakes': 2, 'Cheerios': 1}

problem = LpProblem('AisleOptimization', LpMinimize)

# Updated to 3 aisles for testing...
Num_of_Aisles = 3
aisles = range(Num_of_Aisles)

# Each Aisle has 4 shelves and can't have more than 4 shelves filled
Max_Shelves_Aisle = 4

avgsales = sum(sales.values()) / Num_of_Aisles

# The Optimizer can change the Aisle each Product is assigned to try and solve the problem
# value of 1:  assign to this aisle
AislePick = LpVariable.dicts('AislePick', indexs=[(p,a) for p in products for a in aisles], cat='Binary')

#print(AislePick)

# variable to hold the abs diff of aisles sales value...
aisle_diff = LpVariable.dicts('aisle_diff', indexs=aisles, cat='Real')

# constraint:  Limit aisle-shelf capacity
for aisle in aisles:
    problem += lpSum(shelves[product]*AislePick[product, aisle] for product in products) <= Max_Shelves_Aisle

# constraint:  All producst must be assigned to exactly 1 aisle (or the model would make no assignments at all...
#              or possibly make multiple assignements to balance out)
for product in products:
    problem += lpSum(AislePick[product, aisle] for aisle in aisles) == 1

# constraint:  the "positive" aisle difference side of the ABS
for aisle in aisles:
    problem += aisle_diff[aisle] >= \
               lpSum(sales[product]*AislePick[product, aisle] for product in products) - avgsales

# constraint:  the "negative" aisle diff...
for aisle in aisles:
    problem += aisle_diff[aisle] >= \
               avgsales - lpSum(sales[product]*AislePick[product, aisle] for product in products)

# OBJ:  minimize the total diff (same as min avg diff)
problem += lpSum(aisle_diff[aisle] for aisle in aisles)

# My attempt at the Minimization Formula
# First Calculate what the average sales would be if split perfectly between aisles


# Loop through and calculate total sales in each aisle and then subtract from the average
# illegal:  problem += lpSum([sum(v for _, v in value) - avgsales for _, value in itertools.groupby(sorted([(aisle, sales[product]) for product, aisle in AislePick.items()]), lambda x: x[0])]), 'Hits Diff'

# Restriction so each Aisle can only have 4 shelves
# illegal.  You cannot use a conditional "if" statement to test the value of a variable.
#           This statement needs to produce a constraint expression independent of the value of the variable...
# for aisle in range(Num_of_Aisles):
#     problem += lpSum([shelves[prod] for prod, ais in AislePick.items() if ais == aisle]) <= Max_Shelves_Aisle, f"Sum_of_Slots_in_Aislel{aisle}"

problem.solve()

for (p,a) in [(p,a) for p in products for a in aisles]:
    if AislePick[p,a].varValue:
        print(f'put the {p} on aisle {a}')

for a in aisles:
    aisle_sum = sum(sales[p]*AislePick[p,a].varValue for p in products)
    print(f'expectes sales in aisle {a} are ${aisle_sum : 0.2f}')

# for v in problem.variables():
#     print(v.name,'=',v.varValue)

Yields:

Result - Optimal solution found

Objective value:                5.33333333
Enumerated nodes:               22
Total iterations:               1489
Time (CPU seconds):             0.10
Time (Wallclock seconds):       0.11

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.10   (Wallclock seconds):       0.11

put the Fruit Loops on aisle 0
put the Frosted Flakes on aisle 2
put the Cocoa Pebbles on aisle 2
put the Fruitty Pebbles on aisle 1
put the Corn Flakes on aisle 1
put the Cheerios on aisle 0
expectes sales in aisle 0 are $ 26.00
expectes sales in aisle 1 are $ 21.00
expectes sales in aisle 2 are $ 23.00
[Finished in 281ms]