Python中使用scipy Optimize linprog解决赋值问题

Question

当我尝试在 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 个基本变量，并且对于每个赋值，n2 个变量中恰好有 n 个不为零，因此每个 BFS 都是退化的。任何对此的帮助将不胜感激。

注意：我知道我可以通过函数 scipy.optimize.线性和赋值() 来解决这个问题，并且已经做到了这一点，但想通过将此问题作为线性程序运行来比较我的答案。

Answer 1

考虑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 列）。