0575483 20240402214417.020230914235959.9 85151044921 001027998000026 10.1038/s41598-023-31786-3 22 s. E cav_un_epca*03865942045-232213Nature Publishing Group integer programming combinatorial optimization bounded Wang tiling heuristics graph theory cav_un_auth*0454762 Tyburec Marek UTIA-B Matematická teorie rozhodování Department of Decision Making Theory MTR MTR CZ Ústav teorie informace a automatizace AV ČR, v. v. i. cav_un_auth*0018366 Zeman J. CZ http://library.utia.cas.cz/separaty/2023/MTR/tyburec-0575483.pdf https://www.nature.com/articles/s41598-023-31786-3 GX19-26143X GA ČR CZ cav_un_auth*0440774 Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a 1/2 approximation guarantee for arbitrary tile sets, and a 2/3 guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provide very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic. WOS BA 10000 10100 10102 2024 2 RVO:67985556 https://hdl.handle.net/11104/0345382 cav_un_auth*0357942 ČVUT, Fakulta stavební CZ S 4865 Article Multidisciplinary Sciences A MULTIDISCIPLINARYSCIENCES 4.3 0.8 4.8 0.90728 1.061 734947 347 0.9 48.79 3.89 283942 Q1 3.700 22037 Q1 81.7 Q2 Q2 1.05 Q1 81.7 2023 85151044921 SCOPUS PUBMED 001027998000026 WOS cav_un_epca*0386594 Scientific Reports Roč. 13 1 2023 2045-2322 2045-2322 Nature Publishing Group