python - 混合整数编程 - 仓库位置 (Python + GLPK)

Question

我在优化方面相对较新，我正在尝试优化一个关于仓库位置的问题(来自 Coursera 的 pas 类(class)，2 年前)。问题是，已经超过 6 个小时了，它仍然在有 100 个仓库和 1000 个客户的实例上运行。

问题如下。我有一套仓库，可以开也可以不开。打开它们每个都需要花费 s_w。此外，它们都有最大容量 cap_w。 另一方面，有一堆客户端，所有客户端都必须连接到一个(且只有一个)开放仓库。他们每个人都有一个需求 d_c，对于每个客户，每个仓库都有运输成本 t_wc。 显然，我想要的是最小化总成本。

所以，我有一个大小等于仓库总数的数组，称为 x。每个 x[w] 都是一个整数 {0,1}，定义仓库 w 是否开放。 我还有一个由 0 和 1 组成的矩阵，定义哪个仓库为每个客户发货。因此，行数与客户数一样多，列数与仓库数一样多。该矩阵称为 y。如果仓库 w 交付客户 c，则 y[c][w] 为 1，否则为 0。

到目前为止一切顺利。这应该是 MIP 问题。 为了对其进行编码，我使用 PuPL lib( 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

Answer 1

这实际上并不是一个大问题 - 有专门的代码可以解决比这个更大的仓库位置实例，并且像 CPLEX 这样的现成的好的求解器也可以轻松解决它。我不知道 GLPK/PuPL 的效率如何，但很可能他们只是使用简单的 LP/分支定界(这就是他们正在做的事情)花费了太长时间。

您可以尝试的一件事是允许 y 变量是连续的 (0 <= y <= 1) 而不是二进制。这很可能会加快运行时间，因为求解器不必在它们上进行分支。物理解释是，一些客户可以将他们的需求分配到多个仓库。实际上，在大多数解决方案中，很少有可能会被拆分。如果容量足够大，不具有约束力，那么任何需求都不会被分割，即使您允许 y 连续，您也将始终获得二元解决方案。