如何修复PuLP Python中分配优化的约束 [英] How to fix constraints for allocation optimisation in PuLP python

问题描述

背景:

我正在尝试将客户Ci分配给财务顾问Pj.每个客户都有一个策略值xi.我假设分配给每个顾问的客户数量(n)是相同的，并且不能将同一客户分配给多个顾问.因此，每个合作伙伴都将分配如下的政策值:

I am trying to allocate customers Ci to financial advisers Pj. Each customer has a policy value xi. I'm assuming that the number of customers (n) allocated to each adviser is the same, and that the same customer cannot be assigned to multiple advisers. Therefore each partner will have an allocation of policy values like so:

P1 = [x1，x2，x3]，P2 = [x4，x5，x6]，P3 = [x7，x8，x9]

P1=[x1,x2,x3] , P2=[x4,x5,x6], P3=[x7,x8,x9]

我正在尝试寻找最佳分配方案，以最大程度地减少顾问之间的基金价值分散.我将分散定义为基金最高价值(z_max)和最低基金价值(z_min)的顾问之间的差额.

I am trying to find the optimal allocation to minimise dispersion in fund value between the advisers. I am defining dispersion as the difference between the adviser with the highest fund value (z_max) and the lowest fund value (z_min).

因此，此问题的公式为:

The formulation for this problem is therefore:

如果将客户Ci分配给顾问Pj，则yij = 1，否则为0

where yij=1 if we allocate customer Ci to adviser Pj, 0 otherwise

第一个约束条件要求zmax必须大于或等于每个策略值；由于目标函数鼓励使用较小的zmax值，因此这意味着zmax将等于最大策略值.类似地，第二约束将zmin设置为等于最小策略值.第三个约束条件是，必须将每个客户分配给一个顾问.第四条说，每个顾问必须分配n名客户.信用:@ LarrySnyder610

The first constraint says that zmax has to be greater than or equal to each policy value; since the objective function encourages smaller values of zmax, this means that zmax will equal the largest policy value. Similarly, the second constraint sets zmin equal to the smallest policy value. The third constraint says that each customer must be assigned to exactly one adviser. The fourth says that each adviser must have n customers assigned to him/her. Credit: @LarrySnyder610

问题:

当在PulP中实现此问题时，我希望根据约束3和4在173个顾问中分配1740(n x p)个客户.但是，没有获得72036，并且没有获得最佳分配.

When implementing this problem in PulP, I expect 1740 (n x p) customers to be allocated across the 173 advisers based on constraint 3 and 4. However 72036 and no optimal allocation is obtained.

import random 
import pandas as pd
import pulp 


=============================================================================
# SAMPLE DATA 
=============================================================================

n = 10 # number of customers for each financial adviser
c = 414 #number of customers 
p = 174 #number of financial adviser
policy_values = random.sample(range(1, 1000000), c)


set_I = range(c)
set_J = range(p)
set_N = range(n)
x = {i: policy_values[i] for i in set_I} #customer policy values
y = {(i,j): random.randint(0, 1) for i in set_I for j in set_J} # allocation dummies 


model = pulp.LpProblem("Allocation Model", pulp.LpMinimize)

# =============================================================================
# DECISION VARIABLES
# =============================================================================

y_vars  = {(i,j): pulp.LpVariable(cat=pulp.LpBinary, name="y_{0}_{1}".format(i,j)) for i in set_I for j in set_J}
z_max = pulp.LpVariable("Max Policy Value", 0)
z_min = pulp.LpVariable("Min Policy Value", 0)

# =============================================================================
# OBJECTIVE FUNCTION
# =============================================================================

model += z_max - z_min

# =============================================================================
# CONSTRAINTS
# =============================================================================
model += {j: pulp.lpSum(y_vars[i,j] * x[i] for i in set_I) for j in set_J} <= z_max # constraint 1
model += {j: pulp.lpSum(y_vars[i,j] * x[i] for i in set_I) for j in set_J} >= z_min # constraint 2
model += {i: pulp.lpSum(y_vars[i,j] for j in set_J) for i in set_I} == 1 # constraint 3
model += {j: pulp.lpSum(y_vars[i,j] for i in set_I) for j in set_J} == n #constraint 4

# =============================================================================
# SOLVE MODEL
# =============================================================================

model.solve()
print('Optimised model status: '+str(pulp.LpStatus[model.status]))

count=0
for v in model.variables():
    if v.varValue == 1.0:
        count+=1
        #print(v.name, "=", v.varValue)
print(count)
#>>> 72036 # expecting 1740

print('Optimal difference between highest and lowest summed policy_value: ' + str(pulp.value(model.objective)))

我是否需要对目标函数/约束进行更改以实现上述方程式?

Do I need to make changes to the objective function/constraints to implement the above equations?

下面的代码片段尝试实现@Erwin Kalvelagen的建议更改.对于更高的n，p和c值，持续时间仍然非常长:

Below snippet to try and implement @Erwin Kalvelagen's suggested changes. Still has extremely long durations for higher values of n,p and c:

y_sum = {}

# =============================================================================
# DECISION VARIABLES
# =============================================================================

model = pulp.LpProblem("Allocation Model", pulp.LpMinimize)

y_vars = pulp.LpVariable.dicts('y_vars',((i,j) for i in set_I for j in set_J), lowBound=0, upBound = 1, cat=pulp.LpInteger)
z_max = pulp.LpVariable("Max Policy Value")
z_min = pulp.LpVariable("Min Policy Value")
for j in set_J:
    y_sum[j] = pulp.lpSum([y_vars[i,j] * x[i] for i in set_I])

# =============================================================================
# OBJECTIVE FUNCTION
# =============================================================================

model += z_max - z_min

# =============================================================================
# CONSTRAINTS
# =============================================================================

for j in set_J:
    model += pulp.lpSum([y_vars[i,j] for i in set_I]) == n 
    model += y_sum[j] <= z_max
    model += y_sum[j] >= z_min 


for i in set_I:
    model += pulp.lpSum([y_vars[i,j] for j in set_J]) == 1 

推荐答案

一些提示:

1. 通过print(model)
调试
2. 从一个小的数据集开始

3. 没有正确制定约束条件.应该是这样的

1. Debug by print(model)
2. Start with a small data set

3. The constraints are not correctly formulated. It should be something like

for j in set_J:
    model += 1.0e-6 * pulp.lpSum(y_vars[i,j] * x[i] for i in set_I) <= z_max # constraint 1
    model += 1.0e-6 * pulp.lpSum(y_vars[i,j] * x[i] for i in set_I) >= z_min # constraint 2
    model += pulp.lpSum(y_vars[i,j] for i in set_I) == n #constraint 4

for i in set_I:
    model += pulp.lpSum(y_vars[i,j] for j in set_J) == 1 # constraint 3 

1. 如果n*p <> c
，该模型将不可行
2. 详细信息:我们可能应该重写约束1和2.重复长的求和将创建大量非零元素.

1. The model will be infeasible if n*p <> c
2. Detail: we should probably rewrite constraints 1 and 2. Repeating long summations will create a large number of nonzero elements.

这篇关于如何修复PuLP Python中分配优化的约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！