## 6 Numerical Examples
### Tiling Examples Where All Solutions Are Sought
#### 6.2.5 Case 5
The optimal solution corresponds to the first parionino tiling subproblem in Table 4 using 17 copies of \(P_{1}^{+}\), 17 copies of \(P_{1}^{-}\), 5 copies of \(P_{2}^{+}\), and 3 copies of \(P_{3}^{+}\). The parioninoes \(P_{1}^{+}\), \(P_{1}^{-}\), \(P_{2}^{+}\), and \(P_{3}^{+}\) are coloured dark blue, light blue, red, and yellow, respectively. _The first (and only feasible) subproblem took 14.28 s to solve, thus the potential speedup when using the colouring technique is about 1.2\(\times\). We constructed the ILP file, in this case, using the program LPMAKE_PARIOMINOS_FIGURE10. We found an optimal solution using CPLEX for the first subproblem, i.e., using 26 copies of \(P_{1}^{+}\), three copies of \(P_{2}^{-}\), one copy of \(P_{3}^{+}\), and one copy of \(P_{4}^{+}\) (see Figure 21b)._  
**Example 10**. : _Find all ways of tiling the 8 \(\times\) 16 rectangle using the following actoninoes_  
\[\{P_{i}\}_{i=1}^{10}=\]  
_all orientations permitted, with the following numbers of copies:_  
\[(n_{1},n_{2},n_{3},n_{4},n_{5},n_{6},n_{7},n_{8},n_{9},n_{10})=(1,2,1,2,2,1,2, 2,2,1).\]  
_The sum of the areas of the tiles \(8\sum_{k=1}^{8}n_{k}\) equals the area of the target region as required. The associated ILP file, constructed with the program LPMAKE_POLYMINOS_FIGURE11, has \(n=3126\) unknowns, \(m=138\) constraints, and \(f=2989\) free variables. CPLEX found 96 solutions in 163.95 s._  
_Using colouring techniques, we wish to tile the checkerboard coloured region \(\widehat{R}\) shown in Figure 22a, using \(n_{i}\) parioninoes from the sets \(\{P_{i}^{+}\}\) for \(i=1,2,\,\ldots,7\), and \(n_{j}\) parioninoes from the sets \(\{P_{j}^{+},P_{j}^{-}\}\) for \(j=8,9,10\), with_  
\[\{P_{1}^{+},P_{2}^{+},P_{3}^{+},P_{4}^{+},P_{5}^{+},P_{6}^{+},P_{7}^{+},P_{8 }^{+},P_{8}^{-},P_{9}^{+},P_{9}^{-},P_{10}^{+},P_{10}^{-}\}=\] \begin{table}
\begin{tabular}{c c c c c c c c} \hline \(\mathbf{a_{2}^{+}}\) & \(\mathbf{a_{3}^{+}}\) & \(\mathbf{a_{4}^{+}}\) & \(\mathbf{n}\) & \(\mathbf{m}\) & \(\mathbf{f}\) & \# **Solns.** & **Runtime (s)** \\ \hline
0 & 1 & 1 & 282 & 84 & 200 & 105,344 & 14.28 \\ \hline
3 & 0 & 1 & 302 & 84 & 220 & - & 0.03 \\ \hline \end{tabular}
\end{table} 
Table 5: Number of tiling solutions (# solns.) and runtimes in seconds for CPLEX to solve the two parionimo tiling subproblems in Example 9.  
all orientations permitted, where \(P_{i}^{+}=P_{i}^{-}\) for \(i=1\), \(2\),..., \(7\) and \(P_{j}^{+}\
eq P_{j}^{-}\) for \(j=8\), \(9\), \(10\). The parities of the pariominoes are given by_  
\[\{p_{1},p_{2},p_{3},p_{4},p_{5},p_{6},p_{7},+p_{8},-p_{8},+p_{9},- p_{9},+p_{10},-p_{10}\}\] \[=\{0,0,0,0,0,0,0,+2,-2,+2,-2,+4,-4\}.\]  
_The parity equation (see Theorem 1) is given by_  
\[p_{8}a_{8}^{+}+p_{9}a_{9}^{+}+p_{10}a_{10}^{+}=(p+p_{8}n_{8}+p_{9}n_{9}+p_{10}n+ 10)/2\quad\text{for}\quad 0\leq a_{i}^{+}\leq n_{i},\quad i=8,9,10.\]  
_After noting that \(p=0\) we obtain the linear Diophantine equation_  
\[2a_{8}^{+}+2a_{9}^{+}+4a_{10}^{+}=6,\quad 0\leq a_{8}^{+},a_{9}^{+}\leq 2,\quad 0 \leq a_{10}^{+}\leq 1.\]  
_The MATLAB program DIOPHANTINE_BD_NONECATIVE_BOUNDED was used to solve this equation yielding four pariomino tiling subproblems, solved in CPLEX to give the data in Table 6 for the number of pariomino tiling solutions and CPLEX runtimes._  
Figure 22: Target region and a tiling solution for Example 10: (**a**) The target region \(\bar{R}\), a checkerboard coloured \(8\times 16\) rectangle; (**b**) Successful tiling of the target region \(\bar{R}\) using \(16\) octoninoes. The optimal solution corresponds to the first pariomino tiling subproblem in Table 6 with \((a_{8}^{+},a_{8}^{-},a_{9}^{+},a_{9}^{-},a_{10}^{+},a_{10}^{-})=(0,2,1,1,1,0)\). The pariomino \(P_{9}^{+}\) is coloured dark green to distinguish it from \(P_{9}^{-}\), which is coloured light green. _The fourth subproblem took the longest to solve (54.14 s), thus the potential speedup when using the colouring technique is about 3.0\(\times\).