algorithm - 这是一个线性规划问题吗？

Question

我一直在为一个问题而烦恼...整个问题很复杂...但让我尽力解释真正重要的部分...

我有一张图，其中每条边代表相连的两个节点之间的相关性。每个节点都是一个时间进程(TC)(即 400 个时间点)，其中事件将在不同的时间点发生。两个节点之间的相关性定义为重叠事件的百分比。为简单起见，让我们假设每个节点上发生的事件总数与 $tn$ 相同。并且如果两个 TC(节点)有 $on$ 重叠事件(即发生在完全相同时间点的事件)。然后，相关性可以简单地定义为 $on$/$tn$。

现在，我有一个包含 11 个节点的网络；我知道每两个节点之间的相关性。如何为满足关联约束的所有 11 个节点生成 TC？？？

当您知道两者之间的相关性时，很容易对两个节点执行此操作。假设 TC_1 和 TC_2 的相关值为 0.6，这意味着两个 TC 中有 60% 的重叠事件。此外，假设 TC_1 和 TC_2 的事件总数与 $tn$ 相同。将事件放置在两个 TC 中的一个简单算法是首先随机选择 0.6*$tn$ 个时间点，并将它们视为两个 TC 中发生重叠事件的时隙。接下来，随机选择 TC_1 中的 (1-0.6)*$tn$ 个时间点来放置 TC_1 的其余事件。最后，随机选取TC_1中相应时间点没有发生事件的TC_2中的(1-0.6)*$tn$个时间点。

然而，当您考虑一个 3 节点网络时，它开始变得越来越难，其中生成的三个 TC 需要满足所有三个相关约束(即 3 个边)......对于 11 几乎不可能做到这一点-节点网络...

这对你来说有意义吗？如果不是，请告诉我...

我原以为这只是一个计算机科学编程问题......但我越想越像一个线性规划问题，不是吗？

谁有合理的解决方案？我在 R 中执行此操作，但任何代码都可以...

Answer 1

我认为有一种简单的线性规划方法。将解决方案表示为矩阵，其中每一列都是一个节点，每一行都是一个事件。单元格为 0 或 1，表示事件与给定节点关联或不关联。然后，您的相关约束是固定一对列中 11 的数量的约束，相对于每一列中 1 的数量，您实际上已经提前固定了这些数量。

鉴于此框架，如果您将每个可能的行视为一个特定的项目，出现 X_i 次，那么您将具有 SUM_i X_i * P_ij = K_j 形式的约束，其中 P_ij 是 0 或 1，具体取决于可能的行 i 是否具有11 在由 j 计数的那对列中。当然，这对于大量节点来说有点灾难，但是 11 个节点有 2048 行可能，这并非完全无法管理。 X_i 可能不是线性的，但我想它们应该是有理数，所以如果您准备使用惊人数量的行/事件，您应该没问题。

不幸的是，您可能还必须尝试不同的总列数，因为周围潜藏着不平等现象。如果有 N 行并且两列中有 m 和 n 个 1，则该列对中必须至少有 m + n - N 个 11。实际上，您也可以使每列中 1 的公共(public)数量也作为解决方案变量出现 - 这将为您提供一组新的约束，其中 Q_ij 为 0 和 1，具体取决于列行 i 是否在列中有 1 j.

可能有更好的答案潜伏在那里。特别是，生成特定相关性的正态分布随机变量很容易(如果可行)- http://en.wikipedia.org/wiki/Cholesky_decomposition#Monte_Carlo_simulation和(根据 Google R mvrnorm)。考虑一个具有 2^N 行和 2^N-1 列的矩阵，其中填充了 +/-1 的条目。用 N 位的所有组合标记行，用 N 位的所有非零列标记列。用 -1^(行标签和列标签的奇偶性)填充每个单元格。每列都有相等数量的 +1 和 -1 条目。如果将两列逐个元素地组合在一起，您会得到一个不同的列，该列具有相同数量的 +1 和 -1 条目 - 因此它们相互不相关。如果您的 Cholesky 分解为您提供了元素在 [-1, 1] 范围内的矩阵，您可以使用它来组合列，您可以根据特定概率。

这也表明您可能会在原始的线性规划方法中获得例如 15 列，方法是从不是所有可能性的 2^15 个不同行中选择，而是从具有相同可能性的 16 个不同行中选择模式为具有 2^4 行和 2^4-1 列的矩阵，如上所述。