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.
Here's a quick rundown of the rules:
- There are various building types
- Every building type has a different size
- Every building type has a different range (explained later)
- Every building may give a non-zero base score when placed
- Every building may have give a positive, zero or negative score based on what buildings are within its range when placed
- 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.
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:
pyare each building coordinates
tis the build order (integer)
placed_beforeis a NxN array saying if building i is to be placed before building j (binary)
north_ofhave similar logic (binary)
coversstates whether building j is in range of building i (binary)
y_overlapscheck whether two buildings are built on top of each other, which is restricted (binary)
gives_scoreis 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:
- Lines 140-147 state the building order constraints, which form variable
- 149-161 decide if buildings are east-west and north-east, used for later
- 163-183 establish whether buildings overlaps each other, in the east-west (x) direction and the north-south (y) direction
- 185-219 establish if building i covers building j, filling in the
- 222-237 enforces the separation of two buildings, if they overlap in both x and y directions
- 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.
- 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.