Bounded Wang tilings with integer programming and graph-based heuristics

0575483 - ÚTIA 2024 RIV US eng J - Článek v odborném periodiku
Tyburec, Marek - Zeman, J.
Bounded Wang tilings with integer programming and graph-based heuristics.
Scientific Reports. Roč. 13, č. 1 (2023), č. článku 4865. ISSN 2045-2322. E-ISSN 2045-2322
Grant ostatní: GA ČR(CZ) GX19-26143X
Institucionální podpora: RVO:67985556
Klíčová slova: integer programming * combinatorial optimization * bounded Wang tiling * heuristics * graph theory
Obor OECD: Applied mathematics
Impakt faktor: 4.6, rok: 2022
Způsob publikování: Open access
http://library.utia.cas.cz/separaty/2023/MTR/tyburec-0575483.pdf https://www.nature.com/articles/s41598-023-31786-3

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.
Trvalý link: https://hdl.handle.net/11104/0345382