Modelling Conway's game of life in integer linear programming?

Question

I'm trying to model Conway's game of life rules using integer linear programming, however I'm stuck with one of the rules.

I consider a finite n x n grid. Each cell in the grid is associated with a variable X(i,j) whose value is 0 if the cell is dead and 1 if it is alive.

I'm particularly interested in still lifes, i.e. configurations that, according to the rules, don't change from an instant to the next.

To find them I'm imposing the constraints on the number of neighbours for each cell. So, for an alive cell to remain still it must have 2 or 3 neighbours, and this is easily expressible:

2(1-X(i,j)) + Σ(i,j) >= 2

-5(1 - X(i,j)) + Σ(i,j) <= 3

Where Σ(i, j) is the sum over the neighbours of (i, j) (assume outside of the grid the values are all 0s).

If X(i,j) == 0 then the first addend guarantees that the the constraints are trivially satisfied. When X(i, j) == 1 the constraints guarantee that we have a still life.

The problem is the other rule: for a dead cell to remain dead it must have any number of neighbours different from 3. However, AFAIK you cannot use != in a constraint.

The closest I've come is:

X(i, j) + |Σ(i, j) - 3| > 0

Which does express what I want, but the problem is that I don't think the absolute value can be used in that way (only absolute values of single variables can be expressed. Or is there a way to express this particular situation?).

I wonder, is there a standard way to express the !=? I was thinking that maybe I should use multiple inequalities instead of a single one (e.g. for every possible triple/quadruple of neighbours...), but I cannot think of any sensible way to achieve that.

Or maybe there is some way of abusing the optimization function to penalize this situation and thus, obtaining an optimum would yield a correct solution (or state that it's impossible, depending on the value).

Is anyone able to express that constraint using a linear inequality and the variables X(i, j) (plus, eventually, some new variables)?

Answer 1

The standard way to express

is to express it as

by introducing a new binary variable that indicates which inequality holds true.

This is explained here, at section 7.4.

In a nutshell, if we define y such that

then we need to add the constraints

Where

This is the standard way to model this, but in specific applications there might be better ways. Usually, the tighter the bounds on the sum are, the best the solver performance.