Best way to solve polyominoes packing with OR-Tools (MiniZinc Challenge problem in 2021)

[zayenz]

I am wondering what the best way would be to solve a polyominoes packing problem using OR-Tools.

The background is that I am thinking about solving problems like the packing problem that was used in the MiniZinc Challenge 2021 which was a subset of the problems in minizinc-pentominoes-generator. That model uses an encoding of packing polyominoes into a set of regular language constraints.

Unfortunately, it seems like this model is not very efficient when used with OR-Tools, and I am guessing that the problem is that OR-Tools decomposes the regular constraints into a lot of smaller constraints. For example, in the instance size_10_tiles_10_seed_17_strategy_target with MiniZInc 2.8.3 Gecode (6.3.0) has 110 variables and 10 propagators, while OR-Tools (9.8) has 6.3k Boolean variables and around 15k constraints, and solve time with 10 threads and free search on a M1 Max is around 8.7s for OR-Tools and 0.2s for Gecode. In addition, the regular decomposition is only available for the FlatZinc interface and not if the C++/Python OR-Tools CP-SAT modelling.

What would be a good way to solve polyominos-like packing problems in OR-Tools in a way that works well with OR-Tools?

[Mizux]

https://github.com/MrBenGriffin/or-tools-fun?tab=readme-ov-file#polyomino-puzzle-solver ?

[zayenz]

If I understand the above model correctly, during model construction for each pair of pieces and for each pair of assignments to positions it checks during model construction if that is a valid combination of placements.

In the cases I'm thinking about, the packing sizes are quite a bit larger, but should still be doable with a CP model. In those cases, I think that this encoding might become an issue.

I am thinking about a variant that might be a reasonable middle ground. Consider for each pair of parts p1 and p2 placed in alternative a1 and a2 at some coordinates (x1, y1) and (x2, y2) (for their reference point). For the pair of parts we could pre-calculate the offset (x1 - x2, y1 - y1) projected onto o = (x1 - x2) * M + (y1 - y2) for some suitable M, and for each pair of overlapping positions we could build a table or forbidden assignments.

o  a1  a2
--------
0  .......

I think this could be a position-independent encooding that still outsorces the actual overlap computation to outside the model. The table would be limited in size by the maximum bounding box of either part.

Do you think that would be a usable way to model it? I am still in the exploratory phase for this, so mostly wanted to get some idea on how OR-Tools could be used.

[lperron]

you are mistaking pentominoes and polyominoes.

[zayenz]

Pentominoes are a subset of polyominoes packing (specifically, 5 squares and usually restricted to one copy of each possible tile), so it is not quite incorrect. Most models for pentominoes are usually easily extended to general polyominoes.

Unfortunately I named the repository of packing examples with the wrong name when I created it, that was an just a dumb error.

[lperron]

I have just added a simple cover approach

https://github.com/google/or-tools/blob/main/examples/python/pentominoes_sat.py

[zayenz]

Interesting alternative, and I get why that might be a good approach in OR-Tools. Will have to experiment a bit.