python约束 - 约束金额

Question

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

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

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

每个位置的最大设备数量:( loc1:3, loc2:4, loc3:2 例如最多3个设备loc1等等......)

以及有关位置和设备的一些限制:

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

对于大问题，您可能需要使用字典来加快速度。