在 Google 或工具上定义出现次数
Define number of occurances on Google or-tools
我正在尝试使用 Google Or-tools 在 Python 上构建一个非常简单的测试用例。我有一个包含 20 个整数变量的槽的列表,我试图设置的唯一约束是从 0 到 4 的每个值都出现 3 次。
例如,这将是一个解决方案:
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, -1, -1, -1, -1, -1, -1, -1, -1]
我尝试了以下示例:
from ortools.constraint_solver import pywrapcp
solver = pywrapcp.Solver("test")
num_profs = 5
num_slots = 20
prof_variables = [solver.IntVar(-1, num_profs, "slot{}.prof".format(i)) for i in range(num_slots)]
for prof in range(num_profs):
solver.Add(solver.Sum([prof_variables[i] == prof for i in range(num_slots)]) == 3)
db = solver.Phase(prof_variables, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
#tl = solver.TimeLimit(10000)
solver.NewSearch(db)
count = 0
while solver.NextSolution():
count += 1
print("Time:", solver.WallTime(), "ms")
print()
print("Solution " + str(count))
for i in range(num_slots):
print(prof_variables[i].Value())
if count > 2:
break
solver.EndSearch()
但是,它没有找到任何解决方案(如果我不设置时间限制,它永远不会完成)。
如果我用 Sum
删除约束,这就完成了(根本没有约束)。
由于这个约束非常简单,我希望我写它的方式不正确。知道如何解决吗?
经过更多的尝试,我想我得出了部分结论。我没有寻找数学证明,但尝试使用一些参数,看起来这个算法的时间是指数级的。选择太多意味着该工具无法找到单一的解决方案,而一个非常受限的系统将很快得到解决。
对于我的具体案例,我能够通过改变解决问题的方式来推进。例如,我能够分为 2 个阶段:
- 第一阶段,我将 'prof' 值附加到 'classes',给定了给定的约束。找到了超过 600k 个解决方案,但这非常快(大约 600 毫秒)
- 将 prof/classe 附加到插槽的第二阶段,当我们拥有 link prof/classe.
时存在很多限制
看起来我们表达问题的方式确实很关键,工具需要足够的约束才能非常快速地限制解决方案。
我正在尝试使用 Google Or-tools 在 Python 上构建一个非常简单的测试用例。我有一个包含 20 个整数变量的槽的列表,我试图设置的唯一约束是从 0 到 4 的每个值都出现 3 次。
例如,这将是一个解决方案:
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, -1, -1, -1, -1, -1, -1, -1, -1]
我尝试了以下示例:
from ortools.constraint_solver import pywrapcp
solver = pywrapcp.Solver("test")
num_profs = 5
num_slots = 20
prof_variables = [solver.IntVar(-1, num_profs, "slot{}.prof".format(i)) for i in range(num_slots)]
for prof in range(num_profs):
solver.Add(solver.Sum([prof_variables[i] == prof for i in range(num_slots)]) == 3)
db = solver.Phase(prof_variables, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)
#tl = solver.TimeLimit(10000)
solver.NewSearch(db)
count = 0
while solver.NextSolution():
count += 1
print("Time:", solver.WallTime(), "ms")
print()
print("Solution " + str(count))
for i in range(num_slots):
print(prof_variables[i].Value())
if count > 2:
break
solver.EndSearch()
但是,它没有找到任何解决方案(如果我不设置时间限制,它永远不会完成)。
如果我用 Sum
删除约束,这就完成了(根本没有约束)。
由于这个约束非常简单,我希望我写它的方式不正确。知道如何解决吗?
经过更多的尝试,我想我得出了部分结论。我没有寻找数学证明,但尝试使用一些参数,看起来这个算法的时间是指数级的。选择太多意味着该工具无法找到单一的解决方案,而一个非常受限的系统将很快得到解决。
对于我的具体案例,我能够通过改变解决问题的方式来推进。例如,我能够分为 2 个阶段:
- 第一阶段,我将 'prof' 值附加到 'classes',给定了给定的约束。找到了超过 600k 个解决方案,但这非常快(大约 600 毫秒)
- 将 prof/classe 附加到插槽的第二阶段,当我们拥有 link prof/classe. 时存在很多限制
看起来我们表达问题的方式确实很关键,工具需要足够的约束才能非常快速地限制解决方案。