python - 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

您可以使用像 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。