python约束-约束金额

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 package/not 使用任何包，如果有人有任何建议也是个好主意...）

Answer 1

这很简单assignment-like型号：

所以我们有一个二进制变量指示设备 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

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

Answer 2

编辑： 我在看到@ErwinKalvelagen 的代码之前写了这个答案。所以我没有检查他的解决方案...

所以我使用@ErwinKalvelagen 方法并创建了一个代表问题的矩阵。对于每个 (i,j)，如果设备 i 可以到达位置 j，则 x[i,j]=1，否则为 0。

然后，我对每一行使用 addConstraint(MaxSumConstraint(maxAmount[i]), row) - 这是表示每个位置的最大设备数的约束。

每列

和 addConstraint(ExactSumConstraint(1), col) - 这是每个设备只能放置在一个位置的约束。

接下来，我取了所有 x[i,j]=0（设备 i 不能在位置 j）和每个 t(i,j) addConstraint(lambda var, val=0: var == val, (t,))

这个问题类似于数独问题，我使用了this例子来帮助

我上面例子的矩阵是：

(devices:) 1 2 3 4 5 6 7
     loc1: 1 0 1 0 0 0 1
     loc2: 1 0 1 1 1 1 1
     loc3: 0 1 0 1 1 1 0

我的代码：

        problem = Problem()
        rows = range(locations_amount)
        cols = range(devices_amount)
        matrix = [(row, col) for row in rows for col in cols]
        problem.addVariables(matrix, range(0, 2)) #each cell can get 0 or 1
        rowSet = [zip([el] * len(cols), cols) for el in rows]
        colSet = [zip(rows, [el] * len(rows)) for el in cols]

        rowsConstrains = getRowConstrains() # list that has the maximum amount in each location(3,4,2) 
                                            #from my example: loc1:3, loc2:4, loc3:2 

        for i,row in enumerate(rowSet):
            problem.addConstraint(MaxSumConstraint(rowsConstrains[i]), row)
        for col in colSet:
            problem.addConstraint(ExactSumConstraint(1), col)

        s = getLocationsSet() # set that has all the tuples that x[i,j] = 1

        for i, loc in enumerate(locations_list):
            for j, iot in enumerate(devices_list):
                t=(i,j)
                if t in s:
                    continue
                problem.addConstraint(lambda var, val=0: var == val, (t,)) # the value in these cells must be 0

        solver = problem.getSolution()

解决方案示例：

(devices:) 1 2 3 4 5 6 7
     loc1: 1 0 1 0 0 0 1
     loc2: 0 0 0 1 1 1 0
     loc3: 0 1 0 0 0 0 0

python约束-约束金额

python Constraints - constraining the amount

python

constraints

constraint-programming