math - 从昂贵的搜索到整数规划或约束规划？

Question

考虑 m × n 矩阵 M，其所有条目均为 0 或 1。对于给定的 M，问题是是否存在非零向量 v，其所有条目均为 -1、0 或 1，其中 Mv = 0。例如，

      [0 1 1 1]
M_1 = [1 0 1 1]
      [1 1 0 1]

在这个例子中，没有这样的向量 v。

      [1 0 0 0]
M_2 = [0 1 0 0]
      [0 0 1 0]

在此示例中，向量 (0,0,0,1) 给出 M_2v = 0。

给定一个 m 和 n，我想找出是否存在这样一个 M，以便不存在非零 v 使得 Mv = 0。

如 m = 3和 n = 4那么答案是肯定的，正如我们在上面看到的那样。

我目前正在通过尝试所有不同的 M 和 v 来解决这个问题，这非常昂贵。

However, is it possible to express the problem as an integer programming problem or constraint programming problem so I can use an existing software package, such as SCIP instead which might be more efficient.

Answer 1

这个问题可能比编程更数学。我还没有找到最终答案，但至少有一些想法在这里:

我们可以通过以下方式重新陈述问题。

Problem A: Fix positive integers m and n. Let S be the set of n-dimensional vectors whose entries are 0 or 1. Does there exist any m by n matrix M whose entries are 0 or 1, such that, for any two different vectors v_1 and v_2 in S, the vectors Mv_1 and Mv_2 are different. (Or, you may say that, the matrix M, considered as an application from n-dimensional vectors to m-dimensional vectors, is injective on the set S.)

简而言之:给定对 (m, n) ，是否存在这样的单射 M ?

问题 A 等价于原始问题。确实，如果 Mv_1 = Mv_2用于两个不同的 v_1和 v_2在 S ，那么我们有 M(v_1 - v_2) = 0 ，和向量 v_1 - v_2将只有 0 , 1 , - 1作为条目。反之亦然。

另一种重新解释是:

Problem B: Let m, n be a positive integer and S be the set of n-dimensional vectors whose entries are 0 and 1. Can we find m vectors r_1, ..., r_m in S, such that, for any pair of different vectors v_1 and v_2 in S, there exists an r_i, which satisfies <v_1, r_i> != <v_2, r_i>? Here <x, y> is the usual inner product.

简而言之:我们可以选择 m吗？ S 中的向量区分 S中的每一个人通过将内积与选定的内积一起使用？

问题 B 等价于问题 A，因为您可以识别矩阵 M与 m S 中的向量.

下面，我将自由使用这两种问题的描述。

让我们调用这对 (m, n)如果问题 A(或 B)的答案是 ，则为“ 好对 ”是 .

通过问题 B 的描述，很明显，对于给定的 n ，有一个极小的 m使得 (m, n)是很好的一对。让我们写信 m(n)对于这个最小的 m关联到 n .

类似地，对于给定的 m ，有一个最大值 n使得 (m, n)很好。这是因为，如果 (m, n)很好，即有一个单射 M如问题 A 所述，那么对于任何 n' <= n , 删除任何 n - n' M 的列会给一个单射 M' .让我们写信 n(m)对于这个最大值 n关联到 m .

所以任务变成计算函数 m(n)和/或 n(m) .

我们首先证明几个引理:

Lemma 1: We have m(n + k) <= m(n) + m(k).

证明:如果 M是 m(n)来自 n对的单射矩阵 (m(n), n)和 K是 m(k)来自 k对的单射矩阵 (m(k), k) ，然后是 (m(n) + n(k))来自 (n + k)矩阵

[M 0]
[0 K]

为这对工作 (m(n) + 1, n + 1) .要看到这个，让 v_1和 v_2是任意一对不同的 (n + k)维向量。我们可以把它们都切成两部分:第一个 n条目，以及最后一个 k条目。如果它们的前几块不相等，则可以通过第一个 m(n) 中的一个来区分它们。上述矩阵的行；如果它们的第一块相等，那么它们的第二块必定不同，因此它们可以通过最后一个 m(k)来区分。上述矩阵的行。

Remark: The sequence m(n) is thus a subadditive sequence.

一个简单的推论:

Corollary 2: We have m(n + 1) <= m(n) + 1, hence m(n) <= n.

证明:取 k = 1在引理 1 中。

请注意，来自 m(n) 的其他已知值你可以获得更好的上限。例如，由于我们知道 m(4) <= 3 , 我们有 m(4n) <= 3n .无论如何，这些总是给你 O(n)上限。

下一个引理给你一个下界。

Lemma 3: m(n) >= n / log2(n + 1).

证明:让 T是一套 m(n)条目位于 {0, 1, ..., n} 中的维向量.任意 m(n)来自 n矩阵 M给出来自 S 的 map 至 T , 发送 v至 Mv .

由于存在 M使得上面的映射是单射的，那么集合的大小必然是 T至少是集合的大小 S . T尺寸是 (n + 1)^m ，以及 S 的大小是 2^n ，因此我们有:
(n + 1)^m(n) >= 2^n
或等效地， m(n) >= n / log2(n + 1) .

回到编程

我不得不说我还没有想出一个好的算法。
您可以将问题重新表述为 Set Cover Problem ， 如下:

让 U是一套 n带有条目的维向量 1 , 0或 - 1 ，然后让 S如上所述。每个向量 w在 S给出一个子集 C_w的 U : C_w = {v in U: <w, v> != 0} .那么问题来了:我们能找到 m吗？矢量 w使得子集的并集 C_w等于 U .

一般的集合覆盖问题是 NP 完全问题，但在上面的 Wiki 链接中有一个整数线性规划公式。

无论如何，这不能比 n = 10 带你走得更远。 ， 我猜。

如果我有进一步的结果，我会继续编辑这个答案。