Python中的优化问题

Question

我需要解决一个问题。我有5个设备，每个设备都有4种输入/输出类型。而且我有一个目标的输入/输出组合。第一步，我想找出这些设备之间的所有组合，使得所选设备的总输入/输出数量都等于或大于目标值。让我来解释一下：

# Devices=[numberof_AI,numberof_AO,numberof_BI,numberof_BO,price]

Device1=[8,8,4,4,200]
Device1=[16,0,16,0,250]
Device1=[8,0,4,4,300]
Device1=[16,8,4,4,300]
Device1=[8,8,2,2,150]

Target=[24,12,16,8]

还有一些限制条件。在组合中，最多只能有5个设备。

在第二步，在找到的组合中，我会选择成本最低的一个。

其实，我已经用Python的for循环解决了这个问题，效果很好。但是即使我使用了cython，运行起来还是很慢。

对于这种问题，我还有什么其他的解决方案可以尝试呢？

Answer 1

你也可以用Gustavo Niemeyer开发的Python Constraint模块来解决这个问题。

import constraint

Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

Target=[24,12,16,8]

devices = [Device1, Device2, Device3, Device4, Device5]
vars_number_of_devices = range(len(devices))
max_number_of_devices = 5

problem = constraint.Problem()
problem.addVariables(vars_number_of_devices, range(max_number_of_devices + 1))
problem.addConstraint(constraint.MaxSumConstraint(max_number_of_devices), vars_number_of_devices)
for io_index, minimum_sum in enumerate(Target):
    problem.addConstraint(constraint.MinSumConstraint(minimum_sum, [device[io_index] for device in devices]), vars_number_of_devices)

print min(problem.getSolutions(), key=lambda distribution: sum([how_many * devices[device][-1] for device, how_many in distribution.iteritems()]))

这样会产生以下结果：

{0: 2, 1: 1, 2: 0, 3: 0, 4: 0}

所以，最优的解决方案是2个Device1，1个Device2，0个Device3，0个Device4，0个Device5。

（注意，这里的变量是用从零开始的索引命名的。Device1对应0，Device2对应1，依此类推。）

Answer 2

只需检查所有组合。因为你只有5个设备，所以最多有 6^5=7776 种可能性（因为每个位置可能不使用，所以要用 6）。然后对于每一种可能性，你检查它是否符合你的标准。我不明白为什么这会花费那么多时间。

下面的脚本在我的机器上计算这些东西几乎不需要一秒钟。

d1=[8,8,4,4,200]
d2=[16,0,16,0,250]
d3=[8,0,4,4,300]
d4=[16,8,4,4,300]
d5=[8,8,2,2,150]
dummy=[0,0,0,0,0]

t=[24,12,16,8]

import itertools
def computeit(devicelist, target):
    def check(d, t):
        for i in range(len(t)):
            if sum([dd[i] for dd in d]) < t[i]:
                return False
        return True
    results=[]
    for p in itertools.combinations_with_replacement(devicelist, 5):
        if check(p, t):
            results.append(p)
    return results

print(computeit([d1,d2,d3,d4,d5,dummy],t))

需要Python 2.7。

Answer 3

你可以使用一个叫做 PuLP 的线性规划工具包。（注意，这个还需要你安装一个叫做 GLPK 的库。）

下面是如何用它来解决你给出的例子的：

import pulp

prob = pulp.LpProblem("example", pulp.LpMinimize)

# Variable represent number of times device i is used
n1 = pulp.LpVariable("n1", 0, 5, cat="Integer")
n2 = pulp.LpVariable("n2", 0, 5, cat="Integer")
n3 = pulp.LpVariable("n3", 0, 5, cat="Integer")
n4 = pulp.LpVariable("n4", 0, 5, cat="Integer")
n5 = pulp.LpVariable("n5", 0, 5, cat="Integer")

# Device params
Device1=[8,8,4,4,200]
Device2=[16,0,16,0,250]
Device3=[8,0,4,4,300]
Device4=[16,8,4,4,300]
Device5=[8,8,2,2,150]

# The objective function that we want to minimize: the total cost
prob += n1 * Device1[-1] + n2 * Device2[-1] + n3 * Device3[-1] + n4 * Device4[-1] + n5 * Device5[-1]

# Constraint that we use no more than 5 devices
prob += n1 + n2 + n3 + n4 + n5 <= 5

Target = [24, 12, 16, 8]

# Constraint that the total I/O for all devices exceeds the target
for i in range(4):
    prob += n1 * Device1[i] + n2 * Device2[i] + n3 * Device3[i] + n4 * Device4[i] + n5 * Device5[i] >= Target[i]

# Actually solve the problem, this calls GLPK so you need it installed
pulp.GLPK().solve(prob)

# Print out the results
for v in prob.variables():
    print v.name, "=", v.varValue

运行这个程序非常快，我得到了 n1 = 2 和 n2 = 1，其他的都是 0。