Python PuLP 优化问题 - 最小化与平均值的偏差
Python PuLP Optimization Problem - Minimize Deviation from Average
我正在尝试使用 PuLP 解决优化问题，但我在编写 objective 函数时遇到问题。
我已将现实生活中的示例简化为使用麦片的更简单的示例。因此，假设我有一个产品列表和一些我可以将它们放入的过道（对于此示例 2）。每个产品都有一个我们通常每周销售的数量（例如：我们每周销售 20 盒 Fruit Loops 和 6 盒 Cheerios）。每个项目还需要一定数量的货架（例如：磨砂片需要 1 个货架，但玉米片需要 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
每个过道只有4个货架。所以理论上我可以将 Fruit Loops 和 Corn Flakes 放在一个过道中（2 个货架 + 2 个货架）。如果我将它们放在一个过道中，该过道的每周销售额将为 20 + 12 = 32。如果我将其他 4 件商品（1 个货架 + 1 + 1 + 1）放入一个过道中，那么该过道的销售额将为 15 + 8 + 9 + 6 = 38。过道的平均销售额应为 35。我的优化问题的目标是使每个过道尽可能接近该平均数。我想最小化每个过道每周总销售额与平均数之间的总绝对差异。在这个例子中，我的偏差是 ABS(38-35) + ABS(32-35) = 6。这是我想要最小化的数字。
我不知道怎么写，所以 PuLP 接受了我的 objective。我无法在网上找到具有这种复杂程度的示例，它将每个值与平均值进行比较并计算累积绝对偏差。当我写出技术上会计算出 PuLP 似乎不接受它的代码时。
下面是一些示例代码：
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()
我得到的结果是-3
如果我 运行 LpStatus[problem.status] 我得到 Undefined。我假设我的 objective 函数太复杂了，但我不确定。
感谢任何帮助。
您的主要问题是 ABS 函数是非线性的。 （你试图做的任何排序也是如此......;））。所以你必须重新制定。这样做的典型方法是引入一个辅助变量并考虑与 ABS 函数分开的“正”和“负”偏差，因为这两者都是线性的。网站上有几个这样的例子，包括我刚才回答的这个：
这引入了将过道选择纳入索引的需要，因为您需要有一个用于过道总和或差异的索引。那也不算太难。
然后您必须（如下所示）施加约束以将新的 aisle_diff 变量限制为大于 ABS 的正偏差或负偏差。
所以，我认为下面的工作正常。请注意，我引入了第 3 个过道以使其更多 interesting/testable。我对你现在死掉的代码留下了一些评论。
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)
产量：
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]
我正在尝试使用 PuLP 解决优化问题，但我在编写 objective 函数时遇到问题。
我已将现实生活中的示例简化为使用麦片的更简单的示例。因此，假设我有一个产品列表和一些我可以将它们放入的过道（对于此示例 2）。每个产品都有一个我们通常每周销售的数量（例如：我们每周销售 20 盒 Fruit Loops 和 6 盒 Cheerios）。每个项目还需要一定数量的货架（例如：磨砂片需要 1 个货架，但玉米片需要 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 |
每个过道只有4个货架。所以理论上我可以将 Fruit Loops 和 Corn Flakes 放在一个过道中（2 个货架 + 2 个货架）。如果我将它们放在一个过道中，该过道的每周销售额将为 20 + 12 = 32。如果我将其他 4 件商品（1 个货架 + 1 + 1 + 1）放入一个过道中，那么该过道的销售额将为 15 + 8 + 9 + 6 = 38。过道的平均销售额应为 35。我的优化问题的目标是使每个过道尽可能接近该平均数。我想最小化每个过道每周总销售额与平均数之间的总绝对差异。在这个例子中，我的偏差是 ABS(38-35) + ABS(32-35) = 6。这是我想要最小化的数字。
我不知道怎么写，所以 PuLP 接受了我的 objective。我无法在网上找到具有这种复杂程度的示例，它将每个值与平均值进行比较并计算累积绝对偏差。当我写出技术上会计算出 PuLP 似乎不接受它的代码时。
下面是一些示例代码：
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()
我得到的结果是-3
如果我 运行 LpStatus[problem.status] 我得到 Undefined。我假设我的 objective 函数太复杂了，但我不确定。
感谢任何帮助。
您的主要问题是 ABS 函数是非线性的。 （你试图做的任何排序也是如此......;））。所以你必须重新制定。这样做的典型方法是引入一个辅助变量并考虑与 ABS 函数分开的“正”和“负”偏差，因为这两者都是线性的。网站上有几个这样的例子，包括我刚才回答的这个：
这引入了将过道选择纳入索引的需要，因为您需要有一个用于过道总和或差异的索引。那也不算太难。
然后您必须（如下所示）施加约束以将新的 aisle_diff 变量限制为大于 ABS 的正偏差或负偏差。
所以，我认为下面的工作正常。请注意，我引入了第 3 个过道以使其更多 interesting/testable。我对你现在死掉的代码留下了一些评论。
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)
产量：
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]