## 7 Performance Analysis  
We make some observations about the numerical results presented in Section 6; however, it is hard to make general conclusions because of the many situations that arise (see Figure 12). Some problems do not split into subproblems, or do not do so usefully. We give a summary of the potential speedup results in Table 7.  
Figure 25: The tiling solution for Example 13 using 384 copies of the V-shaped pentomino, and 384 copies of the L-shaped pentomino. The optimal solution uses 384 copies of \(P_{1}^{-}\) (coloured blue) and 384 copies of \(P_{2}^{+}\) (coloured yellow). The target region \(\widehat{R}\) is a checkerboard coloured \(60\times 64\) rectangle with the top left square white. Most problems do split into multiple, smaller subproblems. This has advantages if we are seeking a single solution, or all solutions because we can work in parallel. When a problem splits into multiple parionino tiling subproblems, the experiments show that the CPLEX runtimes for the subproblems roughly correlate with the number of solutions found (see Example 8). Thus a subproblem with the greatest runtime is more likely to be small compared to the runtime of the full problem if the total number of solutions is uniformly distributed among the subproblems. We also saw that the runtimes for infeasible subproblems were much less than the runtimes for the feasible ones. How a problem splits into subproblems depends on whether we are working with a multihedral or monohedral tiling problem. There are two different situations that yield a splitting of a polyomino tiling problem into multiple parionino tiling subproblems. In the monohedral case, when tiling with \(n_{i}\) copies of a polyomino \(P_{i}\) where \(P_{i}^{+}\
eq P_{i}^{-}\) and \(p_{i}=0\), we automatically obtain \(n_{i}+1\) subproblems to consider (see Example 1). The second situation that yields a splitting is in the multihedral case, where the parity equation in Theorem 1 has multiple solutions. However, we can easily create multihedral problems that do not split by using mostly tiles where \(P_{i}^{+}=P_{i}^{-}\) and hence \(p_{i}=0\). For example, Example 12 behaves essentially like a monohedral problem with two P-shaped pentominoes, as zero parity tiles play no part in the parity equation of Theorem 1. In the monohedral case when using tiles with non-zero parity, or where \(P_{i}^{+}=P_{i}^{-}\) (so \(p_{i}=0\)), the parity equation is trivially solved, which implies there is no splitting of the polyomino tiling problem. The numerical results for the multihedral problems uniformly show a reduction in complexity, as measured by the longest runtime to solve a parionino tiling subproblem. Indeed, we could not find a tiling problem in this situation that did not yield a reduction in complexity. We obtained the greatest gains when the number of unknowns \(n\) and the number of free variables \(f\) for the parionino tiling subproblem is small compared to the corresponding values of the polyomino tiling problem. For monohedral problems, the results were less dramatic. When the full polyomino tiling problem is split into multiple parionino tiling subproblems, we may (see Example 1) or may not (see Example 2) get a reduction in complexity. In the monohedral case, when we use copies of a tile with non-zero parity and apply checkerboard colouring techniques, this has little effect on the associated ILP problem. Thus, any gains in the potential speedup will probably be small. A case in point is Example 5 where both the full polyomino tiling problem and the single associated parionino tiling subproblem had \(n=252\) unknowns and \(f=168\) free variables. We carefully constructed the monohedral Examples 3 and 4 to represent Cases 2 and 3 of the decision tree in Figure 12. Because these are contrived cases, they do not represent typical tiling problems. Regarding tiling problems where we seek a single (optimal) solution with ILP, preliminary results (see Example 13) show excellent promise in reducing the problem complexity in the multihedral case.