Как исправить ограничения для оптимизации размещения в PyLP Python - PullRequest
Новая
       31

Как исправить ограничения для оптимизации размещения в PyLP Python

0 голосов
/ 29 мая 2019

Справочная информация:

Я пытаюсь выделить клиентов Ci финансовым консультантам Pj.Каждый клиент имеет значение политики xi.Я предполагаю, что количество клиентов (n), выделенных каждому советнику, одинаково, и что один и тот же клиент не может быть назначен нескольким консультантам.Поэтому каждому партнеру будет присвоено значение политики следующим образом:

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

Я пытаюсь найти оптимальное распределение, чтобы минимизировать разброс стоимости фонда между консультантами.Я определяю дисперсию как разницу между советником с самой высокой стоимостью фонда (z_max) и самой низкой стоимостью фонда (z_min).

Поэтому формулировка этой проблемы: equations

где yij = 1, если мы назначаем клиента Ci советнику Pj, 0 в противном случае

Первое ограничение говорит, что zmax должно быть больше или равно каждому значению политики;поскольку целевая функция поддерживает меньшие значения zmax, это означает, что zmax будет равно наибольшему значению политики.Аналогично, второе ограничение устанавливает zmin равным наименьшему значению политики.Третье ограничение говорит о том, что каждому клиенту должен быть назначен ровно один консультант.Четвертый говорит, что у каждого консультанта должно быть назначено n клиентов.Кредит: @ LarrySnyder610

Проблема:

При реализации этой проблемы в PulP я ожидаю, что 1740 (nxp) клиентов будут распределены по 173 консультантам на основе ограничения 3 и4. Однако 72036 и оптимального распределения не получено.

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)))

Нужно ли вносить изменения в целевую функцию / ограничения для реализации вышеуказанных уравнений?

РЕДАКТИРОВАТЬ: Ниже приведен фрагмент кода, чтобы попытаться реализовать предложенные @Erwin Kalvelagen изменения.По-прежнему имеет чрезвычайно большую длительность для более высоких значений n, p и 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

Ответы [ 2 ]

2 голосов
/ 30 мая 2019

Некоторые подсказки:

  1. Отладка с помощью print(model)
  2. Начните с небольшого набора данных

  3. Ограничения сформулированы неправильно.Это должно быть что-то вроде 

    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
  4. Модель будет невозможна, если n*p <> c
  5. Подробно: вероятно, нам следует переписать ограничения 1 и 2. Повторение длинных суммирований создаст большое количество ненулевых элементов.
0 голосов
/ 29 мая 2019

Не думаю, что вы можете использовать этот формат для добавления ограничений.Попробуйте использовать этот формат: 

for j in set_J:
    model += pulp.lpSum([y_vars[i,j] * x[i] for i in set_I]) <= z_max

и т. Д.

Обратите внимание также на [...] внутри lpSum(...).

Наконец, я не думаю, что вы можете объявлять переменные так, как вы это делали.Я обычно использую LpVariable.dicts(), как в: 

y_vars = pulp.lpVariable.dicts('y_vars', set_I, 0, 1, pulp.LpInteger)
...