Acta Polytechnica CTU Proceedings doi:10.14311/APP.2017.13.0135 Acta Polytechnica CTU Proceedings 13:135–141, 2017 © Czech Technical University in Prague, 2017 available online at http://ojs.cvut.cz/ojs/index.php/app OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES Marek Tyburec∗, Jan Zeman Czech Technical University in Prague, Faculty of Civil Engineering, Department of Mechanics, Thákurova 7, 166 29 Prague 6, Czech Republic ∗ corresponding author: marek.tyburec@fsv.cvut.cz Abstract. Wang tiles proved to be a convenient tool for the design of aperiodic tilings in computer graphics and in materials engineering. While there are several algorithms for generation of finite-sized tilings, they exploit the specific structure of individual tile sets, which prevents their general usage. In this contribution, we reformulate the NP-complete tiling generation problem as a binary linear program, together with its linear and semidefinite relaxations suitable for the branch and bound method. Finally, we assess the performance of the established formulations on generations of several aperiodic tilings reported in the literature, and conclude that the linear relaxation is better suited for the problem. Keywords: Wang tiles, binary and continuous linear programming, semidefinite programming, aperiodic tilings, relaxation. 1. Introduction Wang tiles, squares with colored edges, were invented by and named in honor of Hao Wang, originally serv- ing as a tool for studying the ∀∃∀ decidability problem of the predicate calculus [1]. Wang showed that the decidability problem is equivalent to the domino prob- lem: assume a set of non-rotatable unit-sized (Wang) tiles with edges colored according to the ∀∃∀ problem. If it is feasible to cover the infinite plane by translating copies of the tiles, such that all their vertices lie at the integer lattice points of the plane and the adjoining edges share the same color, the problem is said to be solvable; unsolvable otherwise. For an illustration of a sample 2 × 3 Wang tiling, see Fig. 1. In [2], Wang made a fundamental conjecture stating that the domino problem is solvable if and only if the tiling was periodic, i.e., if there existed a rectangular region of the tiling with identically colored horizontal, and vertical edges, respectively. A year later, Kahr reduced the Turing machine halt- ing problem [3, 4] into the origin-constrained domino problem [5], which implies the domino problem is also undecidable. This can be illustrated by introducing a Turing machine for each tile set, halting only if the domino problem is unsolvable. However, there is an infinite number of such tile sets, making the domino problem undecidable as well, and forbidding existence of a general finite algorithm for the generation of infinite tilings. 1.1. Aperiodic Tile Sets Undecidability of the domino problem was also proved by Wang’s student Berger, who used the principle of expanding squares for developing the sets of 20, 426 [6] and 104 tiles [7] that admit only aperiodic tilings of the infinite plane, contrary to the Wang fundamental conjecture. ✓ ✗ Figure 1. Periodic tiling composed of 2 Wang tiles over 2 colors. Aiming to simplify the Berger’s proof, smaller aperi- odic sets of Wang tiles have been constructed. In 1966, Läuchli sent to professor Wang an aperiodic set of 40 tiles over 16 colors, but it remained unpublished until 1975 [8]. Meanwhile, unaware of Läuchli’s result, Knuth simplified Berger’s set to 92 tiles over 26 col- ors [9]; and Robinson developed sets of 104 and 52 tiles in 1967 [10], of 56 tiles over 12 colors in 1971 [11], and marked existence of a set of 35 tiles [11]. In 1973, Penrose developed a new approach based on kites and darts tiling, leading to a set of 34 tiles. Robinson, being in contact with Penrose, modified the Penrose’s approach to reach a reduced set of 32 tiles over 16 colors [12]. Using the same technique together with Penrose rhombs tiling, Grünbaum obtained a set of 24 tiles over 9 colors in 1987 [12]. Another two tile sets were discovered due to Am- mann. In 1978, he used Ammann bars to reach 16 tiles over 6 colors [13]. Building on the Ammann’s A2 tiling, see, e.g., [12], Robinson obtained a set of 24 tiles over 24 colors in 1977. Subsequent size reduction of the smallest aperi- odic set occurred in 1996, as Kari developed a new method based on Mealy machines multiplying Beatty sequences, and presented a set of 14 tiles over 6 col- ors [14]. Čulík, using the same approach, reduced the set even further to 13 tiles over 5 colors [15]. 135 http://dx.doi.org/10.14311/APP.2017.13.0135 http://ojs.cvut.cz/ojs/index.php/app Marek Tyburec, Jan Zeman Acta Polytechnica CTU Proceedings The search for the minimal aperiodic set is con- cluded by Jeandel, who used a brute-force enumera- tion approach to find aperiodic sets of 11 tiles over 4 and 5 colors; and proved both that there does not exist an aperiodic set with 10 or fewer tiles and with less than 4 colors [16]. In addition to the classical Wang tiles, in 2006, La- gae introduced a subset of the Wang tiles, the corner tiles, with the connectivity information stored in the colored corners instead of the edges [17]. In the same year, he constructed an aperiodic set of 44 corner tiles over 6 colors [18]. The set was further simplified by Nurmi to 30 corner tiles over 6 colors [19]. Note that because the corner tiles can be straightforwardly con- verted to the edge-based Wang tiles [17], our approach naturally extends to the corner tiles, see Section 4 for a specific example. 1.2. Selected Applications Due to the ability of some tile sets to generate ape- riodic patterns, Wang tiles received a broad interest among disciplines. Also, their original significance for automated theorem proving [2] was supplemented by proofs in cellular automata theory [20]. In 2003, Cohen et al. introduced Wang tiles to the computer graphics community [21]. Since then, Wang tiles have been successfully used, e.g., for efficient synthesis of stochastic textures or for generation of Poisson disk distributions. Molecular realization of Wang tiles is due to Win- free, who introduced a self-assembly of biological nanostructures into aperiodic crystals [22]. Novák was probably the first one who used Wang tiles in materials engineering for efficient compres- sion of microstructures [23]; Doškář for their re- construction [24]. Doškář further generated large stochastic samples of the Alporas® foam and its finite- element representations in [25]. In [26], Tyburec used Wang tiles to describe modular assembly of struc- tures, whereas both the topology and arrangement of modules were subjects of optimization. 1.3. Tiling Generation Algorithms Existing tiling generation algorithms are designed specifically to the tile sets they handle. In com- puter graphics, for example, it is essential to gen- erate visually appealing patterns quickly, which is best achieved with stochastic tile sets. Tiling a finite area has then a O(n) complexity, adopting, e.g., the stochastic tiling [21], or the hash-based direct stochas- tic tiling [27] algorithms. The latter algorithm allows straightforward definition of boundary conditions. In the case of mathematical logic, it is crucial to prove that an investigated tile set can tile the whole infinite plane, and does so only aperiodically. As the problem is undecidable, no general algorithm exists, and thus all the algorithms need to exploit the spe- cific structure of each individual (family of) tile sets. Although the algorithms are fast, they remain tile set dependent. All tilings of finite-sized areas are re- stricted to be subsets of the infinite plane, which is not required in the finite domain, and it is almost impossible to introduce boundary conditions. On top of that, there provably exist aperiodic tile sets that admit only non-recursive tiling [28, 29], forbidding design of any problem-specific algorithm to tile the infinite plane. To the authors’ knowledge, the only method that has been used for tiling of finite-sized areas by arbi- trary tile sets is the backtracking algorithm, see [30]. Although the algorithm is general, it is generally inef- ficient, as it commonly creates impossible assemblies too early. Moreover, distant boundary conditions make the problem more difficult to solve. 1.4. Contributions This paper aims to overcome the shortcomings of the methods outlined in the previous section, and to develop an approach that handles tiling of finite- sized areas using arbitrary tile sets, together with a straightforward approach to define edge- or tile- based boundary conditions. Our exposition is structured as follows. In Section 2, we develop a binary linear programming representa- tion of the tiling generation problem. The formulation is relaxed, and its linear and semidefinite approxima- tions are presented. In order to show generality of the formulations, we introduce their extensions to solve the tile-packing problem, to prove that a tile set can not tile the plane, and to prove that a tile set admits periodic tiling. The relaxations are finally employed in a branch and bound method in Section 3 and their performance is assessed in Section 4. 2. Optimization Problem Formulation 2.1. Valid Tiling Consider a finite rectangular area A of the size nt,h × nt,w, with nt,h and nt,w denoting its height and width, respectively. Placing Wang tiles (of a unit size) from the tile set T , such that their vertices lie at the integer lattice points of A, we obtain a tiling with nt,h rows and nt,w columns of tiles. Each tile k ∈ {1, .. , nt} from the tile set T , with nt denoting the number of tiles, is described by the 4-tuple (nk, wk, sk, ek), assigning color codes C to the north, west, south, and east edge of the tile, respec- tively. In any valid tiling, for any two adjacent tiles k and `, with the tile ` being placed in the east of k, it holds that ek = w`. (1) Similarly, for any two vertically adjacent tiles k and m, with the tile m being placed in the south of k, it stands that sk = nm. (2) Both the cases are illustrated in Fig. 2. 136 vol. 13/2017 Optimization Approach to Tiling of Finite Areas With Wang Tiles sm nm wm em s` n` w` e` sk nk wk ek Figure 2. Horizontal, and vertical connectivity among tiles k-`, and k-m, respectively. 2.2. Binary Linear Programming Formulation Let x ∈ {0, 1}nt,h·nt,w·nt denote a binary vector de- scribing the placement of individual tiles within A. The vector consists of all the xi,j,k variables, where i ∈{1, .. , nt,h} and j ∈{1, .. , nt,w} are the row and column iterators, respectively. Let us also define xi,j,k = { 0 if the tile k is not at (i, j), 1 if the tile k is at (i, j). (3) Because each position is occupied by a single tile, we have ∑ k∈T xi,j,k = 1, ∀i ∈H,∀j ∈W. (4) The compatibility constraint (1) can be written in terms of x after realizing that the number of tiles at (i, j) that have east edge colored by c ∈ C has to be equal to the number of tiles at (i, j + 1) with west edge colored also by c. Consequently, we have∑ k∈T xi,j,k[ek = c] − ∑ k∈T xi,j+1,k[wk = c] = 0. (5) As the sums in Eq. (5) are either equal to 0 or 1, resulting from Eq. (4), only two options are possible: If the edge is colored by c, the relation simplifies to 1 − 1 = 0, (6) otherwise, it equals to 0 − 0 = 0, (7) showing that (5) remains valid in both cases. After applying the same approach to Eq. (2) and writing constraints through the entire area A, we obtain the following binary linear program: min x 0 (8a) s.t. ∑ k∈T xi,j,k[ek = c] − ∑ k∈T xi,j+1,k[wk = c] = 0, ∀c ∈C,∀i ∈H,∀j ∈W \{nt,w}, (8b) ∑ k∈T xi,j,k[sk = c] − ∑ k∈T xi+1,j,k[nk = c] = 0, ∀c ∈C,∀j ∈W,∀i ∈H\{nt,h}, (8c) ∑ k∈T xi,j,k = 1, ∀i ∈H,∀j ∈W, (8d) xi,j,k ∈{0, 1}, ∀i ∈H,∀j ∈W,∀k ∈T . (8e) Despite the program (8) being formulated straight- forwardly, it is hard to solve in this original form due to the (non-convex) integrality constraint (8e). Note that the problem is NP-complete because of its combinatorial nature [31]. 2.3. Linear Programming Relaxation In order to make the problem (8) easier to solve, let us relax the integrality constraint (8e) into a linear form 0 ≤ xi,j,k ≤ 1, ∀i ∈H,∀j ∈W,∀k ∈T . (9) Clearly, Eq. (9) allows for all configurations of (8e), but additionally also intermediate non-binary values. In addition, because the constraints in (8) are linear, the resulting approximation is convex and reads as min x 0 (10a) s.t. ∑ k∈T xi,j,k[ek = c] − ∑ k∈T xi,j+1,k[wk = c] = 0, ∀c ∈C,∀i ∈H,∀j ∈W \{nt,w}, (10b) ∑ k∈T xi,j,k[sk = c] − ∑ k∈T xi+1,j,k[nk = c] = 0, ∀c ∈C,∀j ∈W,∀i ∈H\{nt,h}, (10c) ∑ k∈T xi,j,k = 1, ∀i ∈H,∀j ∈W, (10d) 0 ≤ xi,j,k ≤ 1, ∀i ∈H,∀j ∈W,∀k ∈T . (10e) 2.4. Semidefinite Programming Relaxation The integrality constraint (8e) can be rewritten using the non-convex quadratic constraint x2i,j,k − xi,j,k = 0, ∀i ∈H,∀j ∈W,∀k ∈T , (11) which is satisfied only if xi,j,k = {0, 1}, being thus equivalent to (8e). This quadratic form does not simplify the solution, because the problem is still NP-complete, but we will use it for the derivation of a semidefinite programming relaxation. Let us now substitute the binary variables x ∈{0, 1} with y ∈{−1, 1}, which requires x = 1 2 (y + 1). (12) Inserting this into Eq. (3) yields yi,j,k = { −1 if the tile k is not at (i, j), 1 if the tile k is at (i, j). (13) Consequently, we can write a non-convex quadrati- cally-constrained optimization program in terms of y 137 Marek Tyburec, Jan Zeman Acta Polytechnica CTU Proceedings min y 0 (14a) s.t. ∑ k∈T (yi,j,k + 1)[ek = c] − ∑ k∈T (yi,j+1,k + 1)[wk = c] = 0, ∀c ∈C,∀i ∈H,∀j ∈W \{nt,w}, (14b) ∑ k∈T (yi,j,k + 1)[sk = c] − ∑ k∈T (yi+1,j,k + 1)[nk = c] = 0, ∀c ∈C,∀j ∈W,∀i ∈H\{nt,h}, (14c) ∑ k∈T yi,j,k = 2 − nt, ∀i ∈H,∀j ∈W, (14d) y2i,j,k = 1, ∀i ∈H,∀j ∈W,∀k ∈T . (14e) Let us further introduce a symmetric matrix Y ∈ Snt,y·nt,x·nt defined as Y = yyT. (15) The definition directly implies that any solution to the quadratically-constrained optimization problem (14) renders the matrix Y positive semidefinite, in our notation Y � 0, and the rank of the matrix Y equal to 1. Moreover, the definition of y constrains all the elements in the main diagonal of Y equal to 1. Consequently, another equivalent formulation to the problem (8) reads as min y,Y 0 (16a) s.t. ∑ k∈T (yi,j,k + 1)[ek = c] − ∑ k∈T (yi,j+1,k + 1)[wk = c] = 0, ∀c ∈C,∀i ∈H,∀j ∈W \{nt,w}, (16b) ∑ k∈T (yi,j,k + 1)[sk = c] − ∑ k∈T (yi+1,j,k + 1)[nk = c] = 0, ∀c ∈C,∀j ∈W,∀i ∈H\{nt,h}, (16c) ∑ k∈T yi,j,k = 2 − nt, ∀i ∈H,∀j ∈W, (16d) diag(Y) = 1, (16e) Y − yyT = 0. (16f) The only non-convex constraint (16f) can be relaxed, see, e.g., [32], into a convex form Y − yyT � 0, (17) and based on the Schur complement lemma equiva- lently rewritten to ( 1 yT y Y ) � 0. (18) Finally, the semidefinite programming relaxation of the binary linear program (8) reads as min y,Y 0 (19a) s.t. ∑ k∈T (yi,j,k + 1)[ek = c] − ∑ k∈T (yi,j+1,k + 1)[wk = c] = 0, ∀c ∈C,∀i ∈H,∀j ∈W \{nt,w}, (19b) ∑ k∈T (yi,j,k + 1)[sk = c] − ∑ k∈T (yi+1,j,k + 1)[nk = c] = 0, ∀c ∈C,∀j ∈W,∀i ∈H\{nt,h}, (19c) ∑ k∈T yi,j,k = 2 − nt, ∀i ∈H,∀j ∈W, (19d) diag(Y) = 1, (19e)( 1 yT y Y ) � 0, (19f) − 1 ≤ y ≤ 1. (19g) 2.5. Extensions Introduced formulations can include additional re- quirements for generated tilings. We list some of them below, but only in terms of x, as substitution of Eq. (12) into developed equations is obvious. 2.5.1. Tile-Based Boundary Conditions There are four types of tile-based boundary conditions. First, we can enforce placement of the tile k ∈T at position (i, j): xi,j,k = 1, i ∈H, j ∈W, k ∈T . (20) Conversely, avoiding the tile k at (i, j) requires xi,j,k = 0, i ∈H, j ∈W, k ∈T . (21) The requirement that the same tile is placed at both (i, j) and (p, q) can be written as xi,j,k − xp,q,k = 0, {i, p}∈H,{j, q}∈W,∀k ∈T . (22) Enforcing different tiles at (i, j) and (p, q) requires xi,j,k+xp,q,k ≤ 1, {i, p}∈H,{j, q}∈W,∀k ∈T . (23) 2.5.2. Edge-Based Boundary Conditions Starting from Eq. (5), we can also easily formulate edge-based boundary conditions. To constrain the north edge at (i, j) to the color c ∈C, we write∑ k∈T xi,j,k[nk = c] = 1, i ∈H, j ∈W, c ∈C. (24) If the north edge at (i, j) has to differ from c, it holds that∑ k∈T xi,j,k[nk = c] = 0, i ∈H, j ∈W, c ∈C. (25) 138 vol. 13/2017 Optimization Approach to Tiling of Finite Areas With Wang Tiles Equal color c of two edges, e.g., of the north edge at (i, j) and of the west edge at (p, q), is provided by∑ k∈T xi,j,k[nk = c] − ∑ k∈T xp,q,k[wk = c] = 0, {i, p}∈H,{j, q}∈W,∀c ∈C. (26) Finally, different coloring of the north edge at (i, j) and the west edge at (p, q) is guaranteed through∑ k∈T xi,j,k[nk = c] + ∑ k∈T xp,q,k[wk = c] ≤ 1, {i, p}∈H,{j, q}∈W,∀c ∈C. (27) 2.5.3. Periodic Tiling Periodic tiling is a tiling with equally colored both horizontal and also both vertical edges. Thus, periodic tiling secures tilability of the infinite plane. Building on the edge-based boundary conditions, a periodic tiling can be enforced by∑ k∈T x1,j,k[nk = c] − ∑ k∈T xnt,h,j,k[sk = c] = 0, ∀j ∈W,∀c ∈C, (28a) ∑ k∈T xi,1,k[wk = c] − ∑ k∈T xi,nt,w ,k[ek = c] = 0, ∀i ∈H,∀c ∈C. (28b) 2.5.4. Tile Packing Problem The tile packing problem, see, e.g., [30], consists in generation of a tiling with periodic boundary condi- tions, and each tile has to be placed exactly once. In order to describe the problem in our framework, we just need to use Eq. (28) together with∑ i∈H ∑ j∈W xi,j,k = 1, ∀k ∈T . (29) 2.5.5. Objective Function Obviously, the developed formulations can contain arbitrary convex objective function. For instance, we can minimize the maximum occurrences of tiles, compose the tiling such that it fits some pattern, etc. 3. The Branch and Bound Method The whole integer design space, i.e., {0, 1} for the lin- ear (10) and {−1, 1} for the semidefinite (19) approx- imation, can be described using a tree data structure, with each node corresponding to variables x, or y. However, as there is exactly one tile per position, it is advantageous to use the nt-ary tree representation in- stead of the binary one, so that the nodes correspond to the positions and branch into nt children, avoiding solution to infeasible programs placing multiple tiles at the same position. Solution to the developed approximations, (10) or (19), corresponds to exploring the root node of the tree. Unfortunately, because the approximations widen the feasible design space, their solution does not assure to solve the original problem (8) due to the design variables being allowed to take non-integer values. In order to overcome that, we branch some nodes of the tree, i.e., gradually fix all variables that correspond to the specific tile position to all possible combinations of integer values, nt in our case. The relaxation is solved in each node, bounding the problem1, hence the name of the method branch and bound [33]. The branching and bounding continues until the optimal (feasible) solution to (8) is found. If no such solution exists, the solution space is proven to be empty and the tiling generation problem infeasi- ble. Without boundary conditions, infeasibility proves the tile set does not tile infinite plane. 3.1. Branching Rule In our implementation, we firstly branch the most promising nodes, in which the integer infeasibility of the convex relaxation is minimal. For the linear relaxation, we have Iinf = ∑ i∈H ∑ j∈W ∑ k∈T (xi,j,k − x2i,j,k), (30) or Iinf = nt,hnt,wnt − ∑ i∈H ∑ j∈W ∑ k∈T y2i,j,k (31) for the semidefinite relaxation. If Iinf = 0, a feasible solution to the original problem was found. 3.2. Variables Ordering In each node to be branched, we have to define vari- ables that will be fixed. It seems to be advantageous to fix the variables corresponding to the most difficult position, i.e., to the position with the highest integer infeasibility. In the case of the linear relaxation, the to-be-fixed position (i, j) requires max ∀i∈H,∀j∈W ∑ k∈T (xi,j,k − x2i,j,k). (32) Similarly, for the semidefinite relaxation we write max ∀i∈H,∀j∈W (nt − ∑ k∈T y2i,j,k). (33) 4. Examples Building upon the previous sections, we implemented a custom branch and bound algorithm in C++. The linear relaxations are solved using Gurobi [34], the semidefinite programming relaxations are optimized by Mosek [35]. As Gurobi contains a build-in state-of- the-art branch and cut algorithm, usable only for the linear relaxations, we also measured its performance. Five tile sets were tested altogether: Jeandel’s 11 tiles over 4 colors [16], Čulík’s 13 tiles [15], Am- mann’s 16 tiles [12], Lauchli’s 40 tiles [12], and Nurmi’s 1Bounding occurs only if an objective fuction is employed. 139 Marek Tyburec, Jan Zeman Acta Polytechnica CTU Proceedings 11(4) [16] 13(5) [15] 16(6) [12] 40(16) [8] 30(6) [19] Tile set Tiling sample LP 5 × 5 0.13 s/12 rel. 0.10 s/14 rel. 0.10 s/17 rel. 0.01 s/1 rel. 0.01 s/1 rel. SDP 5 × 5 12.65 s/78 rel. 11.07 s/27 rel. 21.66 s/33 rel. 360.40 s/121 rel. 126.17 s/31 rel. LP 6 × 6 0.10 s/12 rel. 0.12 s/14 rel. 0.13 s/17 rel. 0.02 s/1 rel. 0.03 s/1 rel. SDP 6 × 6 69.60 s/34 rel. 227.24 s/79 rel. 184.23 s/33 rel. 1517.59 s/121 rel. 1522.72 s/91 rel. LP 15 × 15 151.82 s/2190 rel. over 6000 s 2.15 s/17 rel. 8.52 s/41 rel. 0.13 s/1 rel. LPG 15 × 15 0.06 s/0 rel. 0.09 s/0 rel. 0.39 s/0 rel. 0.79 s/0 rel. 1.49 s/0 rel. LP 20 × 20 1545.94 s/26137 rel. over 6000 s 8.52 s/17 rel. 32.09 s/41 rel. 4.23 s/31 rel. LPG 20 × 20 0.08 s/0 rel. 0.12 s/0 rel. 0.79 s/0 rel. 1.57 s/0 rel. 8.01 s/0 rel. LPG 25 × 25 396.5 s/7368 rel. 0.12 s/0 rel. 1.34 s/0 rel. 2.96 s/0 rel. 23.95 s/0 rel. LPG 30 × 30 390.18 s/3821 rel. 1361.51 s/5950 rel. 2.31 s/0 rel. 5.23 s/0 rel. 48.97 s/0 rel. Table 1. Time demands and solved relaxations count in generation of aperiodic tilings. LP and SDP denote custom developed branch and bound method supplied with the linear and semidefinite relaxation, respectively; LPG stands for Gurobi cut-and-branch method and the linear relaxation. set of 30 corner tiles [19]. The tile sets were selected to sample different construction methods, tile set sizes, and numbers of colors used. Results of the benchmarks, ran on the Intel® Core™ i5-4210H processor, are summarized in Table 1. They indicate that the linear relaxation surpassed the semidefinite one in terms of speed and in the number of explored nodes. The latter results from the property of the simplex algorithm, used for the solution of lin- ear relaxations, to terminate in vertices of the feasible space polytope. These are more likely integer-feasible than an interior point found by the interior-point algo- rithm, used for the solution of semidefinite programs. Comparison of our branch and bound algorithm and Gurobi’s build-in branch and cut, both using the linear relaxation, is even clearer. Our implementation lacks heuristics, parallelism, and generation of cuts, consequently being inefficient for tile sets with large number of degrees of freedom, such as the Čulík one. 5. Conclusions In this contribution, we demonstrated that the tiling generation problem of finite-sized areas can be for- mulated as an integer optimization problem; and we also introduced its linear and semidefinite program- ming relaxations. Both the relaxations were employed in the branch and bound method and benchmarked on five tile sets. The results indicate that the linear relaxation is more suitable for practical applications. 6. Nomenclature List of symbols A Rectangular area C Color set H Set of rows T Tile set W Set of columns c Color iterator ek East edge color of the tile k i Row iterator j Column iterator k, `, m Tile iterators nc Number of colors in C nk North edge color of the tile k sk South edge color of the tile k nt,h Number of rows in H nt,w Number of columns in W xi,j,k Design variable, xi,j,k ∈{0, 1} yi,j,k Design variable, yi,j,k ∈{−1, 1} wk West edge color of the tile k Iinf Integer infeasibility 140 vol. 13/2017 Optimization Approach to Tiling of Finite Areas With Wang Tiles Acknowledgements This work was supported partly by the Grant Agency of the CTU in Prague, SGS17/042/OHK1/1T/11, by the Grant Agency of the Czech Republic, GAČR 15-07299S, by the Ministry of Industry and Trade, MPO FV10202, and by the Technology Agency of the Czech Republic, TAČR TH02020420. References [1] H. Wang. Dominoes and the AEA case of the decision problem. Symposium on the Mathematical Theory of Automata pp. 23–55, 1962. [2] H. Wang. Proving theorems by pattern recognition - II. Bell System Technical Journal 40(1):1–41, 1961. doi:10.1002/j.1538-7305.1961.tb03975.x. [3] A. M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society s2-42(1):230–265, 1937. doi:10.1112/plms/s2-42.1.230. [4] M. Davis. Computability & Unsolvability. Dover Books on Computer Science Series. Dover, 1958. [5] A. S. Kahr, E. F. Moore, H. Wang. Entscheidungsproblem reduced to the ∀∃∀ case. Proceedings of the National Academy of Sciences 48(3):365–377, 1962. [6] R. Berger. The undecidability of the domino problem. 66. American Mathematical Society (AMS), 1966. doi:10.1090/memo/0066. [7] R. Berger. The Undecidability of the Domino Problem. Ph.D. thesis, Harvard University, 1964. [8] H. Wang. Notes on a class of tiling problems. Fundamenta Mathematicae 82(4):295–305, 1975. [9] D. E. Knuth. The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1968. [10] B. Poizat. Une théorie finiement axiomatisable et superstable. Groupe d’étude des théories stables 3(1):1–9, 1980. [11] R. M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae 12(3):177–209, 1971. doi:10.1007/bf01418780. [12] B. Grünbaum, G. C. Shephard. Tilings and patterns. Freeman, 1987. [13] R. M. Robinson. Undecidable tiling problems in the hyperbolic plane. Inventiones Mathematicae 44(3):259–264, 1978. doi:10.1007/bf01403163. [14] J. Kari. A small aperiodic set of Wang tiles. Discrete Mathematics 160(1-3):259–264, 1996. doi:10.1016/0012-365x(95)00120-l. [15] K. Čulík. An aperiodic set of 13 Wang tiles. Discrete Mathematics 160(1-3):245–251, 1996. doi:10.1016/s0012-365x(96)00118-5. [16] E. Jeandel, M. Rao. An aperiodic set of 11 Wang tiles, 2015. arXiv:1506.06492v1. [17] A. Lagae, P. Dutré. An alternative for Wang tiles. ACM Transactions on Graphics 25(4):1442–1459, 2006. doi:10.1145/1183287.1183296. [18] A. Lagae, J. Kari, P. Dutré. Aperiodic sets of square tiles with colored corners. Report CW 460, 2006. [19] T. Nurmi. From checkerboard to cloverfield: Using Wang tiles in seamless non-periodic patterns. Bridges Finland Conference Proceedings 2016. [20] J. Kari. Reversibility of 2d cellular automata is undecidable. Physica D: Nonlinear Phenomena 45(1- 3):379–385, 1990. doi:10.1016/0167-2789(90)90195-u. [21] M. F. Cohen, J. Shade, S. Hiller, O. Deussen. Wang tiles for image and texture generation. ACM Transactions on Graphics 22(3):287, 2003. doi:10.1145/882262.882265. [22] E. Winfree, F. Liu, L. A. Wenzler, N. C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature 394(6693):539–544, 1998. doi:10.1038/28998. [23] J. Novák, A. Kučerová, J. Zeman. Compressing random microstructures via stochastic Wang tilings. Physical Review E 86(4), 2012. doi:10.1103/physreve.86.040104. [24] M. Doškář, J. Novák, J. Zeman. Aperiodic compression and reconstruction of real-world material systems based on Wang tiles. Physical Review E 90(6), 2014. doi:10.1103/physreve.90.062118. [25] M. Doškář, J. Novák. A jigsaw puzzle framework for homogenization of high porosity foams. Computers & Structures 166:33–41, 2016. doi:10.1016/j.compstruc.2016.01.003. [26] M. Tyburec. Modular-topology optimization of truss structures composed of Wang tiles, Master thesis, Czech Technical University in Prague, 2017. doi:10.13140/rg.2.2.23612.85126. [27] A. Lagae, P. Dutré. A procedural object distribution function. ACM Transactions on Graphics 24(4):1442–1461, 2005. doi:10.1145/1095878.1095888. [28] D. Myers. Nonrecursive tilings of the plane. II. Journal of Symbolic Logic 39, 1974. doi:10.2307/2272641. [29] E. Jeandel. On immortal configurations in Turing machines. In Lecture Notes in Computer Science, pp. 334–343. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-30870-3_34. [30] A. Lagae, P. Dutré. The tile packing problem. Geombinatorics 17(1):8–18, 2007. [31] R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pp. 85–103. Springer US, 1972. doi:10.1007/978-1-4684-2001-2_9. [32] S. Boyd, L. Vandenberghe. Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization. In Communications, Computation, Control, and Signal Processing, pp. 279–287. Springer US, 1997. doi:10.1007/978-1-4615-6281-8_15. [33] G. Nemhauser, L. Wolsey. Integer and Combinatorial Optimization. John Wiley & Sons, Inc., 1988. doi:10.1002/9781118627372. [34] Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2017. http://www.gurobi.com. [35] MOSEK ApS. MOSEK Fusion API for C++ 8.1.0.23, 2017. http://docs.mosek.com/8.1/cxxfusion. 141 http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x http://dx.doi.org/10.1112/plms/s2-42.1.230 http://dx.doi.org/10.1090/memo/0066 http://dx.doi.org/10.1007/bf01418780 http://dx.doi.org/10.1007/bf01403163 http://dx.doi.org/10.1016/0012-365x(95)00120-l http://dx.doi.org/10.1016/s0012-365x(96)00118-5 http://arxiv.org/abs/1506.06492v1 http://dx.doi.org/10.1145/1183287.1183296 http://dx.doi.org/10.1016/0167-2789(90)90195-u http://dx.doi.org/10.1145/882262.882265 http://dx.doi.org/10.1038/28998 http://dx.doi.org/10.1103/physreve.86.040104 http://dx.doi.org/10.1103/physreve.90.062118 http://dx.doi.org/10.1016/j.compstruc.2016.01.003 http://dx.doi.org/10.13140/rg.2.2.23612.85126 http://dx.doi.org/10.1145/1095878.1095888 http://dx.doi.org/10.2307/2272641 http://dx.doi.org/10.1007/978-3-642-30870-3_34 http://dx.doi.org/10.1007/978-1-4684-2001-2_9 http://dx.doi.org/10.1007/978-1-4615-6281-8_15 http://dx.doi.org/10.1002/9781118627372 http://www.gurobi.com http://docs.mosek.com/8.1/cxxfusion Acta Polytechnica CTU Proceedings 13:135–141, 2017 1 Introduction 1.1 Aperiodic Tile Sets 1.2 Selected Applications 1.3 Tiling Generation Algorithms 1.4 Contributions 2 Optimization Problem Formulation 2.1 Valid Tiling 2.2 Binary Linear Programming Formulation 2.3 Linear Programming Relaxation 2.4 Semidefinite Programming Relaxation 2.5 Extensions 2.5.1 Tile-Based Boundary Conditions 2.5.2 Edge-Based Boundary Conditions 2.5.3 Periodic Tiling 2.5.4 Tile Packing Problem 2.5.5 Objective Function 3 The Branch and Bound Method 3.1 Branching Rule 3.2 Variables Ordering 4 Examples 5 Conclusions 6 Nomenclature List of symbols Acknowledgements References