在 Google 或工具上定义出现次数

Question

我正在尝试使用 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 删除约束，这就完成了（根本没有约束）。

由于这个约束非常简单，我希望我写它的方式不正确。知道如何解决吗？

Answer 1

经过更多的尝试，我想我得出了部分结论。我没有寻找数学证明，但尝试使用一些参数，看起来这个算法的时间是指数级的。选择太多意味着该工具无法找到单一的解决方案，而一个非常受限的系统将很快得到解决。

对于我的具体案例，我能够通过改变解决问题的方式来推进。例如，我能够分为 2 个阶段：

第一阶段，我将 'prof' 值附加到 'classes'，给定了给定的约束。找到了超过 600k 个解决方案，但这非常快（大约 600 毫秒）
将 prof/classe 附加到插槽的第二阶段，当我们拥有 link prof/classe.

看起来我们表达问题的方式确实很关键，工具需要足够的约束才能非常快速地限制解决方案。

在 Google 或工具上定义出现次数

Define number of occurances on Google or-tools

python

or-tools