Python中的优化问题

Question

我需要解决一个问题。我有5台设备。它们都有4种I/O类型。还有一个目标输入/输出组合。在第一步中，我希望找到设备之间的所有组合，以便所选设备的总I/O数都等于或大于目标值。让我解释一下：

# 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

只需检查所有组合。由于您只有5台设备，因此（最多）可以使用6^5=7776（因为这5个位置中的每一个都可能未使用，所以您必须使用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))

需要Python2.7。

Answer 2

还可以使用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 x设备1，1 x设备2，0 x设备3，0 x设备4，0 x设备5。

（注意，变量是使用基于零的索引命名的。设备1对应于0，设备2对应于1，依此类推。）

Answer 3

您可以使用类似PuLP的线性编程包。（注意，这还需要安装一个LP库，如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。