4

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

我有一个图表，其中每条边代表连接的两个节点之间的相关性。每个节点都是一个时间过程（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_2 中的 (1-0.6)*$tn$ 时间点，其中 TC_1 中对应的时间点没有发生任何事件。

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

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

我在想这只是一个诡计的计算机科学编程问题......但我越想它，它更像是一个线性编程问题，不是吗？

有人有合理的解决方案吗？我在 R 中这样做，但任何代码都可以......

4

3 回答 3

1

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

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

不幸的是，您可能还必须尝试不同的总列数，因为存在不等式。如果有 N 行且两列中有 m 和 n 1，则该列对中必须至少有 m + n - N 11。实际上，您也可以将每列中的常见 1 数作为解决方案变量 - 这将为您提供一组新的约束，其中 Q_ij 为 0 和一个取决于列 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 列的矩阵。

于 2011-07-16T05:54:28.377 回答
0

如果存在解决方案（您可能会遇到没有解决方案的问题），您可以将其表示为线性方程组。

 x1/x2 = b => 
 x1 - b*x2 = 0
 or just
 a*x1 + b*x2 = 0

您应该能够将其转换为求解线性方程组或更精确的齐次线性方程组，因为 Ax=b 中的 b 等于 0。

问题是，由于您有 n 个节点和 n*(n-1)/2 个关系（方程），因此您必须有许多关系并且没有解决方案。

您可以将此问题表示为

最小化 Ax 其中 x > 0 和 xx == konstant

于 2011-07-16T06:19:48.723 回答
0

您可以将其表示为混合整数程序。

假设我们有N节点，并且每个节点都有T总时隙。您想找到这些时间段的事件分配。每个节点都有tn <= T事件。您的图表中有 M总边。在任何一对共享一条边的节点之间i，j你有一个系数

c_ij = overlap_ij/tn

其中overlap_ij是重叠事件的数量。

让x[i,t]是定义为的二进制变量

 x[i,t] = { 1 if an event occurs at time t in node i
        = { 0 otherwise.

那么tn节点发生事件的约束i可以写成：

sum_{t=1}^T  x[i,t] == tn

让e[i,j,t]是定义为的二进制变量

 e[i,j,t] = { 1 if node i and node j share an event a time t
          = { 0 otherwise

让N(i)表示节点 的邻居i。然后我们每次都有t

  sum_{j in N(i)}  e[i,j,t] <= x[i,t]

这表示如果节点的邻居在某个时间发生了共享事件i，t那么节点 在某个时间i必须有一个事件t。此外，如果节点i有两个邻居u并且v，我们不能有e[i,u,t] + e[i,v,t] > 1（意味着两个事件将共享同一个时隙），因为所有邻居的总和小于x[i,t] <= 1。

我们也知道node和 nodeoverlap_ij = tn*c_ij之间一定有重叠的事件。这意味着我们有ij

  sum_{t=1}^T e[i,j,t] == overlap_ij

将所有这些放在一起，您将获得以下 MIP

  minimize  0 
    e, x
  subject to     sum_{t=1}^T x[i,t] == tn, for all nodes i=1,...,N
                 sum_{j in N(i)} e[i,j,t] <= x[i,t],
                       for all nodes i=1,...,N and all time t=1,...,T
                 sum_{t=1}^T e[i,j,t] == overlap_ij for all edges (i,j) 
                                                      between nodes
                 x[i,t] binary for i=1,...,N and t=1,...,T
                 e[i,j,t] binary for all edges (i,j) and t=1,...,T

这里的目标是零，因为你的模型是一个纯粹的可行性问题。该模型共有T*N + M*T变量和N + N*T + M约束。

像Gurobi这样的 MIP 求解器可以解决上述问题，或者证明它是不可行的（即不存在解）。Gurobi 有一个到 R 的接口。

i您可以通过查看解向量来提取第 th 节点的最终事件时间序列x[i,1], x[i,2], ..., x[i,T]。

于 2014-04-12T08:16:54.930 回答