Как ускорить оптимизацию линейного программирования - PullRequest
Новая
       19

Как ускорить оптимизацию линейного программирования

0 голосов
/ 04 июня 2019

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

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

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

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

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

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

У меня есть рабочее решение, использующее пакет оптимизации: PuLP, который находит оптимальное распределение. 

import random 
import pulp 
import time


# DATA

n = 5 # number of customers for each financial adviser
c = 25 # number of customers 
p = 5 # number of financial adviser
policy_values = random.sample(range(1, 1000000), c) # random generated policy values 

# INDEXES

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 

# DECISION VARIABLES

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

y_sum = {}
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 

# SOLVE MODEL

start = time.clock() 
model.solve()
print('Optimised model status: '+str(pulp.LpStatus[model.status]))
print('Time elapsed: '+str(time.clock() - start))

Обратите внимание, что я реализовал ограничения 1 и 2 немного по-другому, добавив дополнительную переменную y_sum, чтобы предотвратить дублирование выражения с большим количеством ненулевых элементов

Проблема

Проблема в том, что для больших значений n, p и c модель занимает слишком много времени для оптимизации.Можно ли внести какие-либо изменения в то, как я реализовал целевую функцию / ограничения, чтобы ускорить решение?

1 Ответ

1 голос
/ 05 июня 2019

Попробуйте использовать коммерческий решатель, такой как Gurobi, с мякотью. Вы должны значительно сократить время решения.

Также проверьте память вашего компьютера, если какой-либо решатель исчерпает память и начинает выполнять подкачку на диск, время решения будет очень долгим.

...