ILP Part 80 — Islanders

This is the eightieth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve Islanders game.

We have different types of buildings. Each building has a size and a range. When building is constructed, it automatically adds points for its base gain and for all buildings in its range constructed earlier (which may be negative). We want to maximize the income.

Let’s start with model:

Each building has a name (for debugging only), range and size, and a base score (points added when the building is constructed).

Next, for each building we’ll create an ILP model:

This has two variables for position, and third variable for build order. It also has an identifier for debugging.

Now, the code:

In lines 1-25 we define buildings. Next, in lines 27-44 we specify points for constructing buildings in ranges. Finally, we ask to build one city center and for houses, just to keep model simple. We also specify that our board side length is 20.

We initialize variables in lines 55-62. Then, we start adding constraints.

First, we make sure that buildings are built on the board (lines 64-68).

Next, we want to make sure that buildings do not overlap. Building size is set to one means that it spans half a field each direction (so it forms a square of size one). To avoid floating point errors we multiply differences by two and not divide. This is in lines 70-83.

Next, we make sure that buildings are constructed in some order (line 86).

Finally, we calculate the cost in lines 88-101

Sample output: