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

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_2 中的 (1-0.6)*$tn$ 时间点，而 TC_1 中对应的时间点没有发生任何事件。

然而，当你考虑一个 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 的常见数量作为解变量 - 这将为您提供一组新的约束，其中 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 列的矩阵。

Answer 2

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

 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 == 常数

Answer 3

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

假设我们有 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]

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

我们还知道节点i和节点j之间一定存在overlap_ij = tn*c_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 接口。

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