我在优化方面相对较新，我正在尝试优化一个关于仓库位置的问题（来自 Coursera 的课程，2 年前）。问题是，它已经超过 6 个小时了，它仍然在一个有 100 个仓库和 1000 个客户的实例上运行。
问题如下。我有一组可以打开或不打开的仓库。打开它们每个都有成本 s_w。此外，它们都有一个最大容量 cap_w。另一方面，有一堆客户端，它们都必须连接到一个（并且只有一个）开放仓库。他们每个人都有一个需求 d_c，对于每个客户，每个仓库都有一个运输成本 t_wc。我想要的，显然是把总成本降到最低。
所以，我有一个大小等于仓库总数 x 的数组。每个 x[w] 是一个整数 {0,1}，定义仓库 w 是否打开。我还有一个由 0 和 1 组成的矩阵，用于定义为每个客户提供哪个仓库。因此，行数与客户数相同，列数与仓库数相同。该矩阵称为 y。如果 waregouse w 交付客户 c，则 y[c][w] 为 1，否则为 0。
到目前为止，一切都很好。这应该是一个 MIP 问题。为了对其进行编码，我使用 PuPL 库（https://pythonhosted.org/PuLP/pulp.html）和 GLPK 来解决它。
现在，这是我的模型：
#!/usr/bin/python
# -*- coding: utf-8 -*-
from pulp import *
def solveIt(inputData):
# parse the input
lines = inputData.split('\n')
parts = lines[0].split()
warehouseCount = int(parts[0])
customerCount = int(parts[1])
warehouses = []
for i in range(1, warehouseCount+1):
line = lines[i]
parts = line.split()
warehouses.append((int(parts[0]), float(parts[1])))
customerDemands = []
customerCosts = []
lineIndex = warehouseCount+1
for i in range(0, customerCount):
customerDemand = int(lines[lineIndex+2*i])
customerCost = map(float, lines[lineIndex+2*i+1].split())
customerDemands.append(customerDemand)
customerCosts.append(customerCost)
x = [LpVariable("x"+str(w),0,1,cat='Integer') for w in range(0,warehouseCount)]
y = [[LpVariable("y"+str(c)+","+str(w),0,1,cat='Integer') for w in range(0,warehouseCount)] for c in range(0,customerCount)]
prob = LpProblem("Warehouse Location",LpMinimize)
#Constraints
# y_cw <= x_w makes sure that no client is delivered by a closed warehouse
for w in range(0,warehouseCount):
for c in range(0,customerCount):
prob += y[c][w] <= x[w]
#A client is served by exactly one warehouse
for c in range(0,customerCount):
affineExpression = []
for w in range(0,warehouseCount):
affineExpression.append((y[c][w],1))
prob += LpAffineExpression(affineExpression) == 1
#For each warehouse, the sum of demand of all the clients it serves is lower than its capacity
for w in range(0,warehouseCount):
affineExpression = []
for c in range(0,customerCount):
affineExpression.append((y[c][w],customerDemands[c]))
prob += LpAffineExpression(affineExpression) <= warehouses[w][0]
#Objective
#The sum of all the warehouses opening plus the transportation costs has to be minimal
affineExpression = []
for w in range(0,warehouseCount):
affineExpression.append((x[w],warehouses[w][1]))
for c in range(0,customerCount):
affineExpression.append((y[c][w],customerCosts[c][w]))
prob += LpAffineExpression(affineExpression)
print "#######################START SOLVING"
status = prob.solve(GLPK(mip=1,msg = 1))
print LpStatus[status]
for w in range(0,warehouseCount):
print value(x[w])
solution = []
for c in range(0,customerCount):
string = ""
whichOne = -1
for w in range(0,warehouseCount):
string += str(value(y[c][w])) + " "
if value(y[c][w]) == 1:
whichOne = w
solution.append(w)
print string+ " "+str(whichOne)
# calculate the cost of the solution
obj = sum([warehouses[x][1]*x[w] for x in range(0,warehouseCount)])
for c in range(0, customerCount):
obj += customerCosts[c][solution[c]]
# prepare the solution in the specified output format
outputData = str(obj) + ' ' + str(0) + '\n'
outputData += ' '.join(map(str, solution))
return outputData
我知道我构建矩阵的方式不是最佳的，但它确实不会花费太长时间。它开始解决，在某个时候我达到了 GLPK 说的点：
OPTIMAL SOLUTION FOUND
Integer optimization begins...
我相信这意味着它解决了 LP，现在它得到整数......但它已经像 6 小时左右而且它一直在进步，仍然是，但没有完成。在较小的情况下，它工作得很好。
我想我的问题是......我的模型有问题吗？我忘记了一些优化？或者这个问题有那么大吗？
此外，关于计算机，它的性能很差：Intel Atom 和 1GB 的 RAM...
谢谢您的帮助！
编辑：这是日期：https ://github.com/ddeunagomez/DiscreteOptimization/blob/master/04_warehouse_location/warehouse/data/wl_100_1 格式为：
NumberOfWarehouses NumberOfCustomers
CapacityWarehouse1 OpeningCostWarehouse1
CapacityWarehouse2 OpeningCostWarehouse2
.....
CapacityWarehouseN OpeningCostWarehouseN
DemandCustomer1
TransportCostW1_C1 TransportCostW2_C1 ....... TransportCostWN_C1
DemandCustomer2
TransportCostW1_C2 TransportCostW2_C2 ....... TransportCostWN_C2
.....
DemandCustomerN
TransportCostW1_CM TransportCostW2_CM ....... TransportCostWN_CM