I have a Mixed-Integer Linear Programming question.

There's this game called Islanders. Pretty graphics, it's about maximizing your score building a small city in a confined island.

[![enter image description here][1]][1]

Here's a quick rundown of the rules:

 1. There are various building types
 1. Every building type has a different size
 1. Every building type has a different range (explained later)
 1. Every building may give a non-zero base score when placed
 1. Every building may have give a positive, zero or negative score based on what buildings are within its range when placed
 1. Buildings already placed are not affected by newer buildings (their score contribution is not updated)

I thought it would be a fun exercise to formulate these rules into an MILP and see what comes out of it.

I have written the attached Python 3 program, using the PuLP library ([link](https://gist.github.com/Georacer/72ae9b037f0b2895ee80ed7d9846153e)).
I have used the default solver ([CBC](https://github.com/coin-or/Cbc)), provided with the installation of PuLP.

There are currently 4 building types encoded, with their base score declared at line 61, the 4x4 cross-score matrix at line 64 and their dimension and range in lines 72 and 75.

In line 82 there is currently stated that there is 1 building of the first type and 3 buildings of the 2nd type to be placed optimally (N=5)

There are several decision variables:

 1. `px` and `py` are each building coordinates
 1. `t` is the build order (integer)
 1. `placed_before` is a NxN array saying if building i is to be placed before building j (binary)
 1. `east_of`, `north_of` have similar logic (binary)
 1. `covers` states whether building j is in range of building i (binary)
 1. `x_overlaps` and `y_overlaps` check whether two buildings are built on top of each other, which is restricted (binary)
 1. `gives_score` is a NxN array saying if building i contributes to the score of building j (is whthin range is is placed before it, binary)

The constraints are as follows:

 1. Lines 140-147 state the building order constraints, which form variable `t`
 1. 149-161 decide if buildings are east-west and north-east, used for later
 1. 163-183 establish whether buildings overlaps each other, in the east-west (x) direction and the north-south (y) direction
 1. 185-219 establish if building i covers building j, filling in the `covers` variable
 1. 222-237 enforces the separation of two buildings, if they overlap in both x and y directions
 1. 239-250 finds out if a building i contributes to the score of building j

Currently, the cost function under optimization is `gives_score`, to maximize the number of buildings which give score to another.

The issue:

  - Currently with 1 of the first building and 4 of the second, the optimization does not finish in reasonable time. 380 constraints are generated.
  - If instead you go for 3 of the second building type, the problem becomes tractable again, finishing in approx. 10s. 228 constraints are generated.
  - Also, if you disable the constraints of lines 222-237, the optimization manages to run, but the buildings overlap.

Any suggestions on the problem formulation or explanations on why this is such a hard problem?

Thank you in advance.

**Bonus:**
Here is an example optimal result for 1 of type-1 building and 3 of type-2:
[![Example optimal result][2]][2]


  [1]: https://i.sstatic.net/ot0jC.jpg
  [2]: https://i.sstatic.net/qGo28.png