如何线性化二元约束

Question

我正在尝试使用线性规划在生命游戏中找到有效的先前状态。

这是我目前拥有的：

board = [[0, 1, 0],
         [0, 1, 0],
         [0, 1, 0]]

width = len(board)
height = len(board[0])

rows = [str(i) for i in range(width)]
cols = [str(i) for i in range(height)]

choices = LpVariable.dicts("is_alive", (rows, cols), 0, 1, cat="Binary")
or_variables = LpVariable.dicts("OR_variable", (rows, cols), 0, 1, cat="Binary")

prob = LpProblem("Game_of_Life_reversal", LpMinimize)
prob += 0, "Arbitary Objective Function"

for r in rows:
    for c in cols:
        cell = choices[r][c]
        neighbours = getNeighbours(r,c, width, height, choices)
        if board[int(r)][int(c)] == 1:
            #If it's alive, and it was previously alive, then it must've had 2 or 3 neighbours
            #If it's alive, and it was previously dead, then it must've had 3 neighbours
            prob += lpSum(neighbours) >= 2 * cell + (1 - cell) * 3
            prob += lpSum(neigbours) <= 3
        else:
            #If it's dead, and was previously alive, then it must've had 0, 1 or 4+ neighbours
            #If it's dead, and was previously dead, then it must've had 0, 1, 2 or 4+ neighbours
            or_var = or_variables[r][c]
            prob += lpSum(neighbours) >= 4 * (1 - or_var)
            prob += lpSum(neighbours) <= cell * or_var + 9 * (1 - or_var) + or_var * (1 - cell) * 2

最后一个约束 prob += lpSum(neighbours) <= or_var + 9 * (1 - or_var) + or_var * (1 - cell) * 2 正在抛出 TypeError: Non-constant expressions cannot be multiplied。

我猜这是因为我在做 or_var * (1 - cell) * 2 这违反了线性。

有解决办法吗？

Answer 1

假设我们有一个 n x n 的网格。我们的变量是 0 <= C(i , j) <= 1 for 1 <= i <= n and 1 <= j <= n.

令 C*(i , j) = 与单元格 (i , j) 的相邻变量关联的变量总和。

例如，如果单元格 (i , j) 不是边框：

C*(i, j) = C(i+1, j) + C(i-1, j) + C(i, j+1) + C(i, j-1) + C (i-1, j-1) + C(i-1, j+1) + C(i+1, j-1) + C(i+1, j+1).

如果是左上角：

C*(1, 1) = C(1 , 2) + C(2 , 2) + C(2 , 1)

以此类推

1 ) 对于不在网格边界内的每个单元格 (i, j)：

1.1) 如果小区现在被占用：

3 - C(i, j) <= C*(i , j) <= 3

1.2) 如果小区现在没有被占用：

令 0 <= x(i , j) <= 1,

4 * x(i , j) <= C*(i , j) <= 8 * x(i , j) + 2 - C(i , j)

2 ) 对于网格边界中的每个单元格 (i , j)：

2.1) 如果单元格是一个角：

2.1.1) 如果小区现在被占用：

使用项目 (1.1) 的相同约束。

2.1.2) 如果小区现在没有被占用：

0 <= C*(i , j) <= 2 - C(i , j)

2.2) 如果单元格是边：

与项目 (1) 相同的约束条件。

现在你得到了 n² 约束，加上最多 n² - 4 个可能定义的 x(i , j) 的约束，再加上 n² 0 <= C(i , j) <= 1 形式的约束。所有约束是线性的。

如何线性化二元约束

How to linearise binary constraints

python

linear-programming

pulp