Проблема назначения с использованием scipy оптимизировать linprog для решения на Python
Я сталкиваюсь с ошибкой при попытке запустить свой код для этой проблемы минимизации стоимости назначения в Python и надеялся, что кто-нибудь сможет объяснить мне, что я здесь сделал неправильно.
Вопрос:
Мой код:
import numpy as np
import time
n = 10 # n: number of jobs/workers
cost = np.random.rand(n,n) # generate an n-by-n random matrix
from scipy.optimize import linprog
c = cost.reshape((n**2,1)) # reshape the cost matrix to a column vector
#row constraints (sum of each row equals 1)
A_eq_rows = np.ones((n, n**2))
b_eq_rows = np.ones(n)
#column constraints (sum of each column equals 1)
A_eq_cols = np.zeros((n, n**2))
for i in range(n):
A_eq_cols[i, i::n] = 1
b_eq_cols = np.ones(n)
#solve for A_eq and
A_eq=np.vstack((A_eq_rows, A_eq_cols))
b_eq=np.hstack((b_eq_rows, b_eq_cols))
start_time = time.time() # start timing
res = linprog(c, None, None, A_eq, b_eq)
end_time = time.time() # end timing
elapsed_LP = end_time - start_time
print("Minimum cost = ", res.fun)
print("Elapsed time = ", elapsed_LP)
Я по-прежнему получаю значение «Минимальная стоимость» как «Нет», и не совсем уверен, что я сделал с этим не так. У меня есть приличное фундаментальное понимание того, как решить эту проблему, но у меня ограниченный опыт решения этой проблемы с помощью Python.
Я знаю, что он имеет n^2 переменных и 2n-1 линейно независимых ограничений. Следовательно, BFS задачи о назначениях имеет 2n-1 базовых переменных, и для каждого назначения ровно n из n2 переменных не равны нулю, поэтому каждая BFS вырождена. Любая помощь в этом будет принята с благодарностью.
ПРИМЕЧАНИЕ. Я знаю, что могу решить эту задачу с помощью функции scipy.optimize.linear_sum_assignment(), и сделал это, но хотел сравнить свой ответ, запустив эту задачу как линейную программу.
Не могли бы вы рассказать об этом подробнее? Я понимаю, что при наличии n рабочих мест и n работников мы хотели бы назначить каждую работу одному работнику, а каждому работнику — одну работу. Если работа j назначена одному работнику i, стоимость назначения равна cij (матрица стоимости). Xij = 1, если задание j назначено работнику i, и Xij = 0, если задание j НЕ назначено работнику i. Насколько я понимаю, это всего лишь транспортная проблема, где все предложения и потребности представляют собой единицы и нули. Я не совсем уверен, как настроить эту задачу 2x2 вместе с ее ограничениями в Python.
Ограничения для задач 2x2: x11+x12=1, x21+x22=1, x11+x21=1,x12+x22=1. Сформируйте из коэффициентов матрицу ЛП (4х4). В каждой строке и каждом столбце должно быть по два ненулевых значения. Запишите эту матрицу на листе бумаги. В вашем A_eq_rows есть 4 ненулевых значения для каждой строки, что явно неверно.
Спасибо, это было полезно. Моя матрица написана правильно. Я просто не знаю, как отразить это в моем коде для A_eq_rows.
Ответы 2
Рассмотрим n=3. Матрица LP должна выглядеть так
x00 x01 x02 x10 x11 x12 x20 x21 x22
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
Как и во всех сетевых моделях, количество ненулевых значений в каждом столбце равно 2.
Заполнить матрицу A может быть сложно, но в этом случае существует простая структура:
import numpy as np
n = 3 # n: number of jobs/workers
cost = np.random.rand(n,n) # generate an n-by-n random matrix
from scipy.optimize import linprog
c = cost.reshape((n**2,1)) # reshape the cost matrix to a column vector
# allocate LP matrix
A = np.zeros((2*n,n*n))
# sum_j x[i,j] = 1 for i=0..,n-1
for i in range(n):
for j in range(n):
A[i,n*i+j] = 1.0 # same column mapping as reshape
# sum_i x[i,j] = 1 for j=0..,n-1
for j in range(n):
for i in range(n):
A[n+j,n*i+j] = 1.0 # same column mapping as reshape
# rhs
b = np.ones(2*n)
res = linprog(c, None, None, A, b)
print(res.message)
print("Minimum cost = ", res.fun)
# print assignment
for i in range(n):
for j in range(n):
if (abs(res.x[n*i+j])>0.0001):
print(f'{i}->{j} with cost {cost[i,j]}')
Действительно, матрица A выглядит так:
array([[1., 1., 1., 0., 0., 0., 0., 0., 0.],
[0., 0., 0., 1., 1., 1., 0., 0., 0.],
[0., 0., 0., 0., 0., 0., 1., 1., 1.],
[1., 0., 0., 1., 0., 0., 1., 0., 0.],
[0., 1., 0., 0., 1., 0., 0., 1., 0.],
[0., 0., 1., 0., 0., 1., 0., 0., 1.]])
Интерфейс матрицы немного примитивен и может быть сложен в использовании. Гораздо более простой способ — использовать инструмент моделирования, такой как PuLP (который автоматизирует сопоставление переменных решения со столбцами LP).
Это не будет особенно хорошо масштабироваться. Оба linprog и milp принимают разреженные матрицы напрямую.
Он хорошо масштабируется, поскольку мы касаемся только ненулевых элементов A. A является разреженным.
В памяти, да? A не обязательно следует рассматривать как плотное представление.
Даже если бы мы говорили не о памяти, а о времени выполнения, у вас есть вложенные for циклы, в которых, как я ожидаю, векторизованная реализация будет более эффективной.
При создании случайных тестовых данных всегда устанавливайте начальное значение для воспроизводимости.
Нет необходимости перебирать i. Вы можете сформировать разреженную матрицу ограничений напрямую.
import numpy as np
import scipy.sparse as sp
from scipy.optimize import linprog
rand = np.random.default_rng(seed=0)
n = 10
c = rand.random((n, n))
eye = sp.eye_array(n)
A = sp.vstack((
# sum over i must equal one (kronecker)
sp.kron(np.ones(n), eye),
# sum over j must equal one (kronecker)
sp.kron(eye, np.ones(n)),
))
result = linprog(c=c.ravel(), A_eq=A, b_eq=np.ones(2*n))
assert result.success, result.message
x = result.x.reshape((n, n)).astype(int)
print(c.round(2))
print(x)
[[0.64 0.27 0.04 0.02 0.81 0.91 0.61 0.73 0.54 0.94]
[0.82 0. 0.86 0.03 0.73 0.18 0.86 0.54 0.3 0.42]
[0.03 0.12 0.67 0.65 0.62 0.38 1. 0.98 0.69 0.65]
[0.69 0.39 0.14 0.72 0.53 0.31 0.49 0.89 0.93 0.36]
[0.57 0.32 0.59 0.34 0.39 0.89 0.23 0.62 0.08 0.83]
[0.79 0.24 0.88 0.06 0.34 0.15 0.45 0.8 0.23 0.05]
[0.4 0.2 0.09 0.58 0.3 0.67 0.2 0.94 0.37 0.11]
[0.63 0.93 0.44 0.95 0.5 0.43 0.62 1. 0.95 0.46]
[0.76 0.5 0.53 0.79 0.41 0.73 0.71 0.93 0.11 0.73]
[0.93 0.97 0.01 0.86 0.98 0.96 0.15 0.97 0.89 0.82]]
[[0 0 0 1 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 1 0 0 0]]
(1) Всегда смотрите res.message (2) Ваше матричное представление неверно. Сначала решите задачу 2x2 (запишите все скалярные ограничения и сформируйте матрицу вручную).