3

对于给定的 n 和 m，我迭代所有 n × m 部分循环矩阵，其条目为 0 或 1。我想查找是否存在一个矩阵，使得不存在具有相同总和的列的两个子集。在这里，当我们添加列时，我们只是按元素进行。我当前的代码通过o​​rtools使用约束编程。这是我的代码。

from scipy.linalg import circulant
import numpy as np
import itertools
from ortools.constraint_solver import pywrapcp as cs

n = 4
m = 6

def isdetecting(matrix):
    solver = cs.Solver("scip")
    X = np.array([solver.IntVar(values) for i in range(matrix.shape[1])])
    X1 = X.tolist()
    for row in matrix:
        x = X[row].tolist()
        solver.Add(solver.Sum(x) == 0)
    db = solver.Phase(X1, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_CENTER_VALUE)
    solver.NewSearch(db)
    count = 0
#Find just one non-zero solution if there is one
    while (solver.NextSolution() and count < 2):
        solution = [x.Value() for x in X1]
        count += 1
    solver.EndSearch()
    if (count == 1):
        return True

values = [-1,0,1]
nosols = 0
for row in itertools.product([0,1],repeat = m):
    M = np.array(circulant(row)[0:n], dtype=bool)
    if isdetecting(M):
        nosols += 1
        print M.astype(int)

该行values = [-1,0,1]允许解中有任意数量的零。如何指定解决方案中允许的确切数量的零？

4

1 回答 1

3

在 or-tools/Python 中有一个可以使用的全局约束 solver.Count()。例子：

 the_count = 1 # number of 0's allowed
 solver.Add(solver.Count(X1, 0,the_count))

其中“the_count”是（平面）数组“X1”中允许的 0 的数量。the_count 可以是常数或决策变量（因此您可以使用进一步的约束来约束该值，或者只是让域完成约束计数的工作，例如域 1..4 将计数限制在 1 到 4 次出现之间）。

“X1”是检查的决策变量数组。第二个参数“0”是要在 X 中计数的值。

solver.Count() 的使用示例：http: //hakank.org/or-tools/young_tableaux.py。

还有一个solver.Count()的泛化，即solver.Distribute（又名Global Cardinality Count，GCC），你可以同时计算/约束多个值。有关如何使用它的示例，请参见我的 deBruijn 序列模型：http: //hakank.org/or-tools/debruijn_binary.py。

于 2014-03-10T17:05:15.307 回答