0

我正在尝试在 Python 上使用 Google Or-tools 构建一个非常简单的测试用例。我有一个包含 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，则完成（根本没有约束）。

由于这个约束非常微不足道，我希望我写它的方式不正确。关于如何解决它的任何想法？

4

1 回答 1

0

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

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

  • 在给定约束的情况下，我将“prof”值附加到“类”的第一阶段。找到了超过 600k 的解决方案，但这非常快（大约 600 毫秒）
  • 将 prof/classe 附加到插槽的第二阶段，当我们拥有链接 prof/classe 时，存在很多限制。

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

于 2018-05-14T21:02:51.193 回答