混合整数编程-仓库位置(Python + GLPK) [英] Mixed Integer Programming - Warehouse Location (Python + GLPK)

问题描述

我在优化方面相对较新，并且我正在尝试优化有关仓库位置的问题(来自2年前Coursera的一次课程).问题是，它已经超过6个小时，并且仍在具有100个仓库和1000个客户的实例上运行.

I am relatively new in optimizationa nd I am trying to optimize a problem (from a pas class in Coursera, 2 years ago) about Warehouse Location. The problem is, its been more than 6 hours and its still running on an instance with 100 warehouses and 1000 customers.

问题如下.我有一套可以打开或不打开的仓库.打开它们中的每一个的成本为s_w.而且，它们都具有最大容量cap_w. 另一方面，有一堆客户，所有客户都必须连接到一个(只有一个)开放式仓库.他们每个人都有需求d_c，对于每个客户，每个仓库都有运输成本t_wc. 我想要的是使总成本最小化.

The problem is the following. I have a set of warehouses that I can either open or not. Opening each of them has a cost s_w. Also, they all have a maximum capcity, cap_w. On the other side, there is a bunch of clients, all of them have to be connected to one (and only one) open warehouse. Each of them has a demand d_c and for each of the clients, there is a transportation cost from each warehouse t_wc. What I want, is obviouly, to minimize the total cost.

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

So, I have an array of size equal to the total number of warehouses called x. Each x[w] is a integer {0,1} defining if warehouse w is open or not. I also have a matrix of 0s and 1s defining which warehouse delivers each customer. there is, therefore as many rows as customers and as many columns as warehouses. The matrix is called y. y[c][w] is 1 if waregouse w delivers customer c, 0 otherwise.

到目前为止，一切都很好.推测这是一个MIP问题. 要进行编码，我使用PuPL lib( https://pythonhosted.org/PuLP/pulp在Python上完成此操作.html )和解决该问题的GLPK.

So far so good. This is supossed to be an MIP problem. To code it, I do it un Python using the PuPL lib(https://pythonhosted.org/PuLP/pulp.html) and the GLPK to solve it.

现在，这是我的模特:

#!/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所说的地步:

I know the way I build the matrix is not optimal, but it really isnt taking too long. It started solving and at some point I reached a point where GLPK said:

OPTIMAL SOLUTION FOUND
Integer optimization begins...

我相信这意味着它解决了LP，现在使它变成整数了……但是大约6个小时左右，并且它一直在进步，现在还在，但是还没有结束. 在较小的情况下，它可以正常工作.

I believe that means it solved the LP, and now its getting it integer... but its been like 6 hours or so and its been progressing, and still is, but doesn't finish. In smaller instances, it worked fine.

我的问题是，我的模型有问题吗?我忘记了一些优化?还是这个问题这么大?

My question, I guess is... Is there something wrong with my model? Some optimizations I forgot? OR is this problem just that huge?

另外，关于计算机，它的性能相当差:Intel Atom和仅1GB的RAM ...

Also, about the computer, its quite a poor one: Intel Atom and 1GB of RAM only...

谢谢您的帮助！

这是日期: https://github.com/ddeunagomez/DiscreteOptimization/blob/master/04_warehouse_location/warehouse/data/wl_100_1 格式为:

Here is the date: https://github.com/ddeunagomez/DiscreteOptimization/blob/master/04_warehouse_location/warehouse/data/wl_100_1 the format is:

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

推荐答案

这在事物方案中并不是真正的大问题-有专门的代码可以解决比这个更大的仓库位置实例，而且效果很好-像CPLEX这样的现成的求解器也可以轻松地对其进行求解.我不知道GLPK/PuPL的效率如何，但是很可能是，使用简单的LP/分支绑定(它们正在做的事情)它们花费的时间太长了.

This is not really a huge problem in the scheme of things -- there is specialized code to solve much larger warehouse location instances than this one, and good off-the-shelf solvers like CPLEX could solve it easily too. I don't know how efficient GLPK/PuPL are, but it could well be that they just take too long using straightforward LP/branch-and-bound (which is what they are doing).

您可以尝试做的一件事是允许y变量是连续的(0< = y< = 1)，而不是二进制的.这很可能会加快运行时间，因为求解程序无需在其上进行分支.实际的解释是，某些客户可以将他们的需求分配到多个仓库之间.实际上，在大多数解决方案中，它们中可能很少.如果容量足够大以至于无法绑定，那么任何需求都不会分裂，即使允许y连续，您也将始终获得二进制解.

One thing you could try is to allow the y variables to be continuous (0 <= y <= 1) instead of binary. This will most likely speed up the run times because the solver won't have to branch on them. The physical interpretation is that some customers can have their demands split between multiple warehouses. In practice, very few of them will probably be split in most solutions. If the capacities are large enough to be non-binding, then none of the demands will be split, and you'll always get binary solutions even though you allow y to be continuous.

这篇关于混合整数编程-仓库位置(Python + GLPK)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！