python Constraints——限制数量

Question

我有一个约束问题，我试图用 python-constraint 来解决

假设我有 3 个位置:loc1,...loc3

此外，我有 7 个设备:device1,...device7

每个位置的最大设备数量:loc1:3, loc2:4, loc3:2(例如，loc1 中最多 3 个设备，依此类推...)

还有一些关于位置和设备的限制:

loc1: device1, device3, device7,

loc2: device1, device3, device4, device5, device6, device7

loc3: device2, device4, device5, device6

(意味着只有 device1、device3 和 device7 可以在 loc1 中。)

我正在尝试为位置中的设备获取一组可能的选项。

    from constraint import *
    problem = Problem()
        for key in locations_devices_dict:
           problem.addVariable(key,locations_devices_dict[key])
           # problem.addVariable("loc1", ['device1', 'device3', 'device7'])
   problem.addConstraint(AllDifferentConstraint())

我一直在思考如何进行约束。我试过:

problem.addConstraint(MaxSumConstraint(3), 'loc1')

但它不起作用，MaxSumConstraint 没有对我需要的求和。

所有设备都必须放置在某处

可能的解决方案:

loc1: device1, device3
loc2: device4, device6, device7
loc3: device2, device5

有人有想法吗？

(另一个python包/不使用任何包，如果有人有任何建议也是个好主意......)

Answer 1

这是一个简单的类似赋值的模型:

所以我们有一个二进制变量指示设备 d 是否分配给位置 L。线性约束只是:

• 将每台设备分配到一个位置
• 每个位置都有最大数量的设备
• 确保只使用允许的赋值(根据 allowed(L,d) 建模)

这个问题可以用任何约束求解器来处理。

列举所有可能的解决方案有点危险。对于大型实例，数量太多了。即使对于这个小问题，我们也已经有 25 个解决方案:

对于大型问题，这个数字将是天文数字。

使用 Python 约束包，这看起来像:

from constraint import *

D = 7 # number of devices
L = 3 # number of locations

maxdev = [3,4,2]
allowed = [[1,3,7],[1,3,4,5,6,7],[2,4,5,6]]

problem = Problem()
problem.addVariables(["x_L%d_d%d" %(loc+1,d+1) for loc in range(L) for d in range(D) if d+1 in allowed[loc]],[0,1])
for loc in range(L):
    problem.addConstraint(MaxSumConstraint(maxdev[loc]),["x_L%d_d%d" %(loc+1,d+1) for d in range(D) if d+1 in allowed[loc]])
for d in range(D):
    problem.addConstraint(ExactSumConstraint(1),["x_L%d_d%d" %(loc+1,d+1) for loc in range(L) if d+1 in allowed[loc]])

S = problem.getSolutions()
n = len(S)
n

对于大型问题，您可能希望使用字典来加快处理速度。