A Parallelizable Integer Linear Programming Approach for Tiling Finite Regions of the Plane with Polyominoes

Abstract

The general problem of tiling finite regions of the plane with polyominoes is NP-complete, and so the associated computational geometry problem rapidly becomes intractable for large instances. Thus, the need to reduce algorithm complexity for tiling is important and continues as a fruitful area of research. Traditional approaches to tiling with polyominoes use backtracking, which is a refinement of the ‘brute-force’ solution procedure for exhaustively finding all solutions to a combinatorial search problem. In this work, we combine checkerboard colouring techniques with a recently introduced integer linear programming (ILP) technique for tiling with polyominoes. The colouring arguments often split large tiling problems into smaller subproblems, each represented as a separate ILP problem. Problems that are amenable to this approach are embarrassingly parallel, and our work provides proof of concept of a parallelizable algorithm. The main goal is to analyze when this approach yields a potential parallel speedup. The novel colouring technique shows excellent promise in yielding a parallel speedup for finding large tiling solutions with ILP, particularly when we seek a single (optimal) solution. We also classify the tiling problems that result from applying our colouring technique according to different criteria and compute representative examples using a combination of MATLAB and CPLEX, a commercial optimization package that can solve ILP problems. The collections of MATLAB programs PARIOMINOES (v3.0.0) and POLYOMINOES (v2.1.4) used to construct the ILP problems are freely available for download.

Keywords

• tiling with polyominoes
• checkerboard colouring arguments
• integer linear programming
• parallelizable algorithm
• algorithm complexity
• MATLAB