Using logical constraints: Conway's Game of Life

This tutorial includes everything you need to set up decision optimization engines, build a mathematical programming model, leveraging logical constraints.

When you finish this tutorial, you'll have a foundational knowledge of Prescriptive Analytics.

This notebook is part of Prescriptive Analytics for Python

It requires either an installation of CPLEX Optimizers or it can be run on IBM Watson Studio Cloud (Sign up for a free IBM Cloud account and you can start using Watson Studio Cloud right away).

This model is greater than the size allowed in trial mode of CPLEX.

Table of contents:

Describe the business problem
How decision optimization (prescriptive analytics) can help
Use decision optimization
Summary

This example is demonstrating Life Game from Robert Bosch and Michael Trick, CP 2001, CPAIOR 2002. using CPLEX

The original paper can be found here It is based on Conway's Game of Life and is a basic integer program with birth constraints.

To begin the game, the player places checkers on some of the cells of the board, creating an initial pattern. A cell with a checker in it is living and those without are dead. The pattern is then modified by applying the following rules over ad over abain.

If a cell has exactly two living neighbors, then its state remain the same in the new pattern (if living, it remains living, if dead it remains dead).
If a cell has exactly three living neightbors, then it is living in the next pattern. This is a birth condition.
If a cell has fewer than 2 or more than 3 living neighbors, then it is dead in the next pattern. These are the death by isolation and death by overcrowding conditions reespectively.

How decision optimization can help

Prescriptive analytics (decision optimization) technology recommends actions that are based on desired outcomes. It takes into account specific scenarios, resources, and knowledge of past and current events. With this insight, your organization can make better decisions and have greater control of business outcomes.
Prescriptive analytics is the next step on the path to insight-based actions. It creates value through synergy with predictive analytics, which analyzes data to predict future outcomes.
Prescriptive analytics takes that insight to the next level by suggesting the optimal way to handle that future situation. Organizations that can act fast in dynamic conditions and make superior decisions in uncertain environments gain a strong competitive advantage.

With prescriptive analytics, you can:

Automate the complex decisions and trade-offs to better manage your limited resources.
Take advantage of a future opportunity or mitigate a future risk.
Proactively update recommendations based on changing events.
Meet operational goals, increase customer loyalty, prevent threats and fraud, and optimize business processes.

Use decision optimization

Step 1: Import the library

Run the following code to import Decision Optimization CPLEX Modeling library. The DOcplex library contains the two modeling packages, Mathematical Programming and Constraint Programming, referred to earlier.



In [ ]:

    
import sys
try:
    import docplex.mp
except:
    raise Exception('Please install docplex. See https://pypi.org/project/docplex/')

A restart of the kernel might be needed if you updated docplex.

Step 2: Set up the prescriptive model



In [ ]:

    
from docplex.mp.model import Model
import math

from collections import namedtuple

Tdv = namedtuple('Tdv', ['dx', 'dy'])

neighbors = [Tdv(i, j) for i in (-1, 0, 1) for j in (-1, 0, 1) if i or j]

assert len(neighbors) == 8



In [ ]:

    
n = 6



In [ ]:

    
assert Model.supports_logical_constraints(), "This model requires logical constraints cplex.version must be 12.80 or higher"



In [ ]:

    
lm = Model(name='game_of_life_{0}'.format(n))
border = range(0, n + 2)
inside = range(1, n + 1)

# one binary var per cell
life = lm.binary_var_matrix(border, border, name=lambda rc: 'life_%d_%d' % rc)

# store sum of alive neighbors for interior cells
sum_of_neighbors = {(i, j): lm.sum(life[i + n.dx, j + n.dy] for n in neighbors) for i in inside for j in inside}

# all borderline cells are dead
for j in border:
    life[0, j].ub = 0
    life[j, 0].ub = 0
    life[j, n + 1].ub = 0
    life[n + 1, j].ub = 0

The sum of alive neighbors for an alive cell is greater than 2



In [ ]:

    
for i in inside:
    for j in inside:
        lm.add(2 * life[i, j] <= sum_of_neighbors[i, j])

The sum of alive neighbors for an alive cell is less than 3



In [ ]:

    
for i in inside:
    for j in inside:
        lm.add(5 * life[i, j] + sum_of_neighbors[i, j] <= 8)

For a dead cell, the sum of alive neighbors cannot be 3



In [ ]:

    
for i in inside:
    for j in inside:
        ct3 = sum_of_neighbors[i, j] == 3
        lm.add(ct3 <= life[i, j])  # use logical cts here

Satisfy the 'no 3 alive neighbors for extreme rows, columns



In [ ]:

    
for i in border:
    if i < n:
        for d in [1, n]:
            lm.add(life[i, d] + life[i + 1, d] + life[i + 2, d] <= 2)
            lm.add(life[d, i] + life[d, i + 1] + life[d, i + 2] <= 2)

Symmetry breaking



In [ ]:

    
n2 = int(math.ceil(n/2))
half1 = range(1, n2 + 1)
half2 = range(n2 + 1, n)

# there are more alive cells in left side
lm.add(lm.sum(life[i1, j1] for i1 in half1 for j1 in inside) >= lm.sum(life[i2, j2] for i2 in half2 for j2 in inside))

# there are more alive cells in upper side
lm.add(lm.sum(life[i1, j1] for i1 in inside for j1 in half1) >= lm.sum(life[i2, j2] for i2 in inside for j2 in half2))

Setting up the objective: find maximum number of alive cells



In [ ]:

    
lm.maximize(lm.sum(life))



In [ ]:

    
# add a dummy kpi
nlines = lm.sum( (lm.sum(life[i,j] for j in inside) >= 1) for i in inside)
lm.add_kpi(nlines, 'nlines')

# parameters: branch up, use heusristics, emphasis on opt, threads free
lm.parameters.mip.strategy.branch = 1
lm.parameters.mip.strategy.heuristicfreq = 10
lm.parameters.emphasis.mip = 2
lm.parameters.threads = 0



In [ ]:

    
# store data items as fields
lm.size = n
lm.life = life



In [ ]:

    
border3 = range(1, lm.size-1, 3)
life_vars = lm.life
vvmap = {}
for i in border3:
    for j in border3:
        vvmap[life_vars[i, j]] = 1
        vvmap[life_vars[i+1, j]] = 1
        vvmap[life_vars[i, j+1]] = 1
        vvmap[life_vars[i+1, j+1]] = 1
ini_s = lm.new_solution(vvmap)



In [ ]:

    
assert ini_s.check(), 'error in initial solution'



In [ ]:

    
lm.add_mip_start(ini_s)

Step 3: Solve the problem with default CPLEX algorithm



In [ ]:

    
assert lm.solve(log_output=True), "!!! Solve of the model fails"
lm.report()



In [ ]:

    
def lifegame_solution_to_matrix(mdl):
    rr = range(0, mdl.size+2)
    life_vars = mdl.life
    array2 = [[life_vars[i, j].solution_value for j in rr] for i in rr]
    return array2



In [ ]:

    
print(lifegame_solution_to_matrix(lm))

Summary

You learned how to set up and use the IBM Decision Optimization CPLEX Modeling for Python to formulate a Mathematical Programming model with logical constraints.

References

Decision Optimization CPLEX Modeling for Python documentation
Decision Optimization on Cloud
Need help with DOcplex or to report a bug? Please go here
Contact us at dofeedback@wwpdl.vnet.ibm.com"



In [ ]: