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

Question

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

mathconstraint-programminginteger-programming

8

考虑一个所有元素均为0或1的 m 行 n 列矩阵 M。对于给定的 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来解决这个问题，这是非常昂贵的。

然而，是否可能将问题表达为整数规划或约束编程问题，以便我可以使用现有的软件包，例如SCIP，这可能更有效。

- Simd

1

答案不总是“是”吗？如果我正确理解了问题，任何一列元素为零的矩阵都可以符合答案。而且这对于任何m和n都是有效的。 - rpsml

1

@rpsml 不，矩阵M可能是方的和规则的，并且问题要求一个具有非零元素的向量。必须检查M是否有一个非平凡的核，其中包含来自{0,1,-1}的非零向量元素。 - Codor

1

@rpsml 我认为你可能误读了问题。我想找到是否存在这样的M，使得不存在非零v满足Mv = 0。 - Simd

@rpsml 抱歉造成困惑。问题是，是否存在一个M，使得不存在一个非零向量v满足Mv = 0。我们可以在stackoverflow上通过聊天的方式进行实时交流吗？ - Simd

1

@dorothy 我改口了。感谢你的澄清。 - rpsml

显示剩余9条评论

3个回答

3

我认为使用布尔矩阵乘法将使您更有效地解决仅涉及 1 和 0 的 Mv=0 问题。使用此方法，您应该能够在不担心右手边等于零的排名缺陷的情况下解决问题。以下是一些关于使用 BMM 的算法的文档链接：http://theory.stanford.edu/~virgi/cs367/lecture2.pdf。

- bern

1

我不确定这如何回答问题。问题是：给定m和n，我想找到是否存在这样的M，以便不存在非零v使得Mv = 0。您的答案如何解决这个问题？ - Simd

虽然它没有给出解决问题的确切代码，但它展示了如何利用数据的布尔特性来执行Ax=0问题。如果不将问题限制在这个集合中，解决方案会变得很差，因为为了解决x，必须将A除以零。使用布尔矩阵代数似乎是解决这个问题的好方法。 - bern

0

如果我理解正确，您正在询问一个给定的 m,n 是否存在一个矩阵 M（线性变换），其核心为平凡核心，即 Ker(M)={0}。

请注意，这与 M 的零空间为零 0 相同，即 Null(M)=0。

对于系统 Mv=0，如果矩阵 M 的秩等于向量 v 的维度，则零空间为{0}。因此，您的问题归结为询问是否存在一个 mxn 矩阵，其秩 dim(v)=m。

该问题的形式已在此处讨论

在一组固定元素上生成特定秩的“随机”矩阵

您也可以用行列式来构造这个问题，因为如果 M 的行列式为0，则零空间为非平凡。因此，您可以考虑使用 {-1,0,1} 中的条目构造具有所需行列式的矩阵。

希望这能帮到您。

- mdh1665

不，那不是完全正确的。内核不允许包含任何元素为-1、0、1的非零向量。它可以包含其他向量，实际上如果元素允许在实数范围内变化，则保证矩阵是非方阵的。 - Simd

啊，我看错了问题。我以为矩阵和向量v中的条目都来自{0,1,-1}，因此你是在{0,1,-1}上的向量空间中工作。对不起。 - mdh1665

此外，“向量空间在 {0, 1, -1} 上”并不存在... 因为该集合不是一个域。 - WhatsUp

@whatUip，你说得完全正确，我是个白痴。由于某种原因，我一直在想F_3，并没有检查我的想法是否有意义。但显然它不是关于+的一个群。我会惭愧地退出。 - mdh1665

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- WhatsUp · Accepted Answer

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

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

问题A: 固定正整数 m 和 n。设 S 为由 0 或 1 组成的 n 维向量集合。是否存在任何一个 m 行 n 列的由 0 或 1 组成的矩阵 M，使得对于 S 中的任意两个不同向量 v_1 和 v_2，向量 Mv_1 和 Mv_2 都不同。（或者说，将矩阵 M 视为从 n 维向量到 m 维向量的函数，在集合 S 上是单射的。）

简言之：给定一对（m，n），是否存在这样的单射M？

问题A等同于原问题。确实，如果对于集合S中的两个不同的v1和v2，Mv1 = Mv2，则我们有M（v1-v2）= 0，并且向量v1-v2将只具有0，1，-1作为条目。反之亦然。

另一种重新解释是：

问题B：设m、n为正整数，S为由0和1组成的n维向量集合。我们能否在S中找到m个向量r_1, ..., r_m，使得对于S中任意两个不同的向量v_1和v_2，都存在一个r_i，满足<v_1, r_i> != <v_2, r_i>？其中<x, y>是通常的内积。

简而言之：我们能否选择m个向量在S中，通过与这些向量的内积来区分S中的每个向量？ 问题B等价于问题A，因为你可以用S中的m个向量来识别矩阵M。

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

让我们称对偶 (m, n) 为“好对”，如果问题A（或B）的答案是“是”。根据问题B的描述，对于给定的n，存在一个最小的m使得(m, n)是一个好对。我们将写m(n)表示与n相关联的这个最小的m。同样，对于给定的m，存在一个最大的n，使得(m, n)是好的。这是因为，如果(m, n)是好的，即存在一个如问题A所述的单射M，那么对于任何n' <= n，擦除M的任何n-n'列将给出一个单射M'。让我们写n(m)表示与m相关联的这个最大的n。因此，任务变成了计算函数m(n)和/或n(m)。

We first prove several lemmas:

Lemma 1: 我们有 m(n + k) <= m(n) + m(k)。

Proof: 如果 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)行之一来区分它们。

备注：因此，序列m(n)是一个次加性序列。

一个简单的推论：

推论2：我们有m(n + 1) <= m(n) + 1，因此m(n) <= n。

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

注意，从其他已知的m(n)值可以得到更好的上界。例如，由于我们知道m(4) <= 3，因此我们有m(4n) <= 3n。无论如何，这些都给出了O(n)的上界。

下一个引理给出了下界。

引理3：m(n) >= n / log2(n + 1)。

证明：设T是所有维度为m(n)且条目位于{0, 1, ..., n}中的向量的集合。任何m(n)乘以n的矩阵M都会给出一个从S到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)。

回到编程问题

我必须说我还没有想出一个好的算法。你可以将问题重新表述为集合覆盖问题，如下所示：

设 U 为由元素为 1、0 或 -1 的向量组成的 n 维向量集合，S 如上所述。对于集合 S 中的每个向量 w，都会有一个由 U 中的向量构成的子集 C_w： C_w = {v in U: <w, v> != 0}。问题是：我们是否可以找到 m 个向量 w，使得所有 C_w 的并集等于 U。

一般的集合覆盖问题是 NP 完全问题，但在上面的维基链接中提供了整数线性规划公式。

无论如何，我猜这不能让你更进一步，当 n = 10 时，我会继续编辑此答案，如果有更多结果。