如何限制约束编程中的零的数量

Question

对于给定的 n 和 m，我会遍历所有 n 行 m 列的部分 循环矩阵，这些矩阵的元素只能是 0 或 1。我想找出是否存在一个矩阵，使得没有两个列的子集的和是相同的。在这里，当我们加列的时候，是逐个元素相加的。我的代码目前是通过 ortools 进行约束编程的。以下是我的代码。

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] 这一行允许解中有任意数量的零。那么我该如何指定解中允许的零的确切数量呢？

Answer 1

在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的数量。这个数量可以是一个固定的值，也可以是一个决策变量（也就是说，你可以通过其他约束来限制这个值，或者让变量的范围自动限制这个数量，比如范围1..4就限制了出现次数在1到4之间）。

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

使用solver.Count()的一个例子可以在这里找到：http://hakank.org/or-tools/young_tableaux.py。

还有一个更通用的工具叫做solver.Distribute（也叫全局基数计数，GCC），它可以同时统计和限制多个值。你可以参考我的deBruijn序列模型，看看它是怎么用的：http://hakank.org/or-tools/debruijn_binary.py。