Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
An Integer Programming Approach to the Irregular Polyomino Tiling Problem
verfasst von : Vadim M. Kartak, Aigul Fabarisova
Erschienen in: Mathematical Optimization Theory and Operations Research
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, new integer programming models of the problem of irregular polyomino tiling are introduced. We consider tiling of finite, square, NxN-sized structure with L-shaped trominoes without any restriction on their number. Each polyomino can be rotated 90\(^{\circ }\), so there are four orientations of the L-tromino. Developed models are effective for small-size instances. For medium- and large-size instances we suggest dividing the initial structure into several equally sized parts and combine the solutions of optimized tilings. We tried to apply new models to the existing information-theoretic entropy-based approach. We conducted computational experiments using IBM ILOG CPLEX package. The problem of irregular polyomino tiling can be applied to the design of phased array antennas where polyomino-shaped subarrays are used to reduce the cost of the array antenna and to reduce the undesired sidelobes radiation. Computational results along with antenna simulation results are presented in the paper.