在整数线性规划中对康威的人生游戏建模？
Modelling Conway's game of life in integer linear programming?
我正在尝试使用整数线性规划对 Conway's game of life 规则进行建模，但是我受困于其中一个规则。
我考虑 有限 n x n 网格。网格中的每个单元格都与一个变量 X(i,j) 相关联，如果该单元格已死则其值为 0，如果它还活着则为 1。
我对静物特别感兴趣，即根据规则，不会从一个瞬间改变到下一个瞬间的配置。
为了找到它们，我对每个单元格的邻居数量施加了限制。因此，要使一个活细胞保持静止，它必须有 2 或 3 个邻居，这很容易表达：
2(1-X(i,j)) + Σ(i,j) >= 2
-5(1 - X(i,j)) + Σ(i,j) <= 3
其中 Σ(i, j) 是 (i, j) 的邻居之和（假设在网格之外的值都是 0）。
如果 X(i,j) == 0 则第一个加数保证约束条件得到满足。当X(i, j) == 1约束保证我们有静物。
问题在于另一条规则：要使死细胞保持死状态，它必须有任意数量的不同于 3 的邻居。
但是，据我所知，您不能在约束中使用 !=。
我最接近的是：
X(i, j) + |Σ(i, j) - 3| > 0
这确实表达了我想要的，但问题是我认为绝对值不能那样使用（只能表达单个变量的绝对值。或者有没有办法表达这个具体情况？）。
我想知道，!=有没有标准的表达方式？
我在想也许我应该使用多个不等式而不是一个不等式（例如，对于每一个可能的 triple/quadruple 邻居......），但我想不出任何明智的方法来实现这一目标。
或者也许有一些方法可以滥用优化函数来惩罚这种情况，因此，获得最优值将产生正确的解决方案（或声明这是不可能的，具体取决于值）。
是否有人能够使用 线性 不等式和变量 X(i, j)（加上最终一些新变量）来表达该约束？
标准的表达方式
表示为
通过引入一个新的二进制变量来指示哪个不等式成立。
第 7.4 节here对此进行了解释。
简而言之，如果我们定义 y 这样
然后我们需要添加约束
哪里
这是建模的标准方法，但在特定应用中可能有更好的方法。通常，总和的界限越紧，求解器的性能最好。
我正在尝试使用整数线性规划对 Conway's game of life 规则进行建模，但是我受困于其中一个规则。
我考虑 有限 n x n 网格。网格中的每个单元格都与一个变量 X(i,j) 相关联，如果该单元格已死则其值为 0，如果它还活着则为 1。
我对静物特别感兴趣，即根据规则，不会从一个瞬间改变到下一个瞬间的配置。
为了找到它们，我对每个单元格的邻居数量施加了限制。因此，要使一个活细胞保持静止，它必须有 2 或 3 个邻居，这很容易表达：
2(1-X(i,j)) + Σ(i,j) >= 2
-5(1 - X(i,j)) + Σ(i,j) <= 3
其中 Σ(i, j) 是 (i, j) 的邻居之和（假设在网格之外的值都是 0）。
如果 X(i,j) == 0 则第一个加数保证约束条件得到满足。当X(i, j) == 1约束保证我们有静物。
问题在于另一条规则：要使死细胞保持死状态，它必须有任意数量的不同于 3 的邻居。
但是，据我所知，您不能在约束中使用 !=。
我最接近的是：
X(i, j) + |Σ(i, j) - 3| > 0
这确实表达了我想要的，但问题是我认为绝对值不能那样使用（只能表达单个变量的绝对值。或者有没有办法表达这个具体情况？）。
我想知道，!=有没有标准的表达方式？
我在想也许我应该使用多个不等式而不是一个不等式（例如，对于每一个可能的 triple/quadruple 邻居......），但我想不出任何明智的方法来实现这一目标。
或者也许有一些方法可以滥用优化函数来惩罚这种情况，因此，获得最优值将产生正确的解决方案（或声明这是不可能的，具体取决于值）。
是否有人能够使用 线性 不等式和变量 X(i, j)（加上最终一些新变量）来表达该约束？
标准的表达方式
表示为
通过引入一个新的二进制变量来指示哪个不等式成立。
第 7.4 节here对此进行了解释。
简而言之，如果我们定义 y 这样
然后我们需要添加约束
哪里
这是建模的标准方法，但在特定应用中可能有更好的方法。通常，总和的界限越紧，求解器的性能最好。