我有一个约束问题,我试图用python-constraint解决
所以假设我有3个位置：loc1,… loc3
另外,我有7个设备：device1,… device7
每个位置的最大设备数量：loc1：3,loc2：4,loc3：2
(例如loc1中最多3个设备,依此类推……)
以及有关位置和设备的一些限制：
loc1：device1,device3,device7,
loc2：device1,device4,device5,device6,device7
loc3：device2,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,device7
loc3: device2,device5
有人有想法吗？
(另一个python包/不使用任何包,如果有人有任何建议也是个好主意…)
最佳答案
这是一个简单的赋值模型：
所以我们有一个二进制变量,指示设备d是否分配给位置L.线性约束只是：
>将每个设备分配到一个位置
>每个位置都有最大数量的设备
>确保仅使用允许的分配(由上面的允许(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,5,6,[2,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),d+1) for loc in range(L) if d+1 in allowed[loc]])
S = problem.getSolutions()
n = len(S)
n
对于大问题,您可能希望使用dicts来加快速度.