Abstract
A polyomino is a generalization of the domino and is created by connecting a fixed number of unit squares along edges. Tiling a region with a given set of polyominoes is a hard combinatorial optimization problem. This paper is motivated by a recent application of irregular polyomino tilings in the design of phased array antennas. Specifically, we formulate the irregular polyomino tiling problem as a nonlinear exact set covering model, where irregularity is incorporated into the objective function using the information-theoretic entropy concept. An exact solution method based on a branch-and-price framework along with novel branching and lower-bounding schemes is proposed. The developed method is shown to be effective for small- and medium-size instances of the problem. For large-size instances, efficient heuristics and approximation algorithms are provided. Encouraging computational results including phased array antenna simulations are reported.
Similar content being viewed by others
References
Adjengue, L., Audet, C., Yahia, I.: A variance-based method to rank input variables of the mesh adaptive direct search algorithm. Optim. Lett. 8(5), 1599–1610 (2014)
Ash, J., Golomb, S.: Tiling deficient rectangles with trominoes. Math. Mag. 77(1), 46–55 (2004)
Audet, C., Dennis Jr, J.E.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17(1), 188–217 (2006)
Avella, P., Sassano, A., Vasil’ev, I.: Computational study of large-scale p-median problems. Math. Program. 109, 89–114 (2007)
Balas, E., Padberg, M.: On the set-covering problem. Oper. Res. 20(6), 1152–1161 (1972)
Balas, E., Padberg, M.: Set partitioning: a survey. SIAM Rev. 18(4), 710–760 (1976)
Barnhart, C., Johnson, E., Nemhauser, G., Savelsbergh, M., Vance, P.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316–329 (1998)
Berge, C., Chen, C., Chvatal, V., Seow, C.: Combinatorial properties of polyominoes. Combinatorica 1(3), 217–224 (1981)
Berger, R.: The undecidability of the domino problem. Mem. Amer. Math. Soc. No. 66, 72 (1966)
Bodini, O.: Tiling a rectangle with polyominoes. Discrete Math. Theor. C pp. 81–88 (2003)
Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)
Cardinal, J., Fiorini, S., Joret, G.: Tight results on minimum entropy set cover. Algorithmica 51, 49–60 (2008)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Combinatorial aspects of l-convex polyominoes. Eur. J. Comb. 28, 1724–1741 (2007)
COIN-OR: Branch-Cut-Price Framework 1.3.1. https://projects.coin-or.org/Bcp (2011)
Dehmer, M., Emmert-Streib, F.: Structural information content of networks: graph entropy based on local vertex functionals. Comput. Biol. Chem. 32(2), 131–138 (2008)
Delest, M., Viennot, G.: Algebraic languages and polyominoes enumeration. Theor. Comput. Sci. 34(1–2), 169–206 (1984)
Demaine, E., Demaine, M.: Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity. Graph Comb. 23, 195–208 (2007)
Duchi, E., Rinaldi, S., Schaeffer, G.: The number of z-convex polyominoes. Adv. Appl. Math. 40, 54–72 (2008)
Fang, S., Rajasekera, J., Tsao, H.: Entropy Optimization and Mathematical Programming. International Series in Operations Research & Management Science. Kluwer, Dordrecht (1997)
Garfinkel, R., Nemhauser, G.: The set-partitioning problem: set covering with equality constraints. Oper. Res. 17(5), 848–856 (1969)
Ghoniem, A., Sherali, H.: Complementary column generation and bounding approaches for set partitioning formulations. Optim. Lett. 3, 123–136 (2009)
Golomb, S.: Tiling with polyominoes. J. Comb. Theory 1, 280–296 (1966)
Golomb, S.: Tiling with sets of polyominoes. J. Comb. Theory 9, 60–71 (1970)
Golomb, S.: Polyominoes: Puzzles, Patterns, Problems, and Packings, 2nd edn. Princeton University Press, Princeton (1994)
Halperin, E., Karp, R.: The minimum-entropy set cover problem. Theor. Comput. Sci. 348(2–3), 240–250 (2005)
Hardy, G., Littlewood, J., Pólya, G.: Inequalities. Cambridge Math. Lib. Cambridge Univ. Press, Cambridge (1952)
Haus, U., Michaels, D., Savchenko, A.: Extended formulations for MINLP problems by value decompositions. In: EngOpt 2008 (2008)
IBM: IBM ILOG CPLEX 12.2. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ (2011)
Jensen, I.: Enumerations of lattice animals and trees. J. Stat. Phys. 102(3/4), 865–881 (2001)
Jones, D., Schonlau, M., Welch, W.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998)
Kapur, J., Kesavan, H.: Entropy Optimization Principles with Applications. Academic Press, London (1992)
Köppe, M., Louveaux, Q., Weismantel, R.: Intermediate integer programming representations using value disjunctions. Discrete Optim. 5(2), 293–313 (2008)
Lee, J.: Constrained maximum-entropy sampling. Oper. Res. 46(5), 655–664 (1998)
Mailloux, R.: Phased array theory and technology. Proc. IEEE 70(3), 246–302 (1982)
Mailloux, R., Santarelli, S., Roberts, T.: Wideband arrays using irregular (polyomino) shaped subarrays. Electron. Lett. 42(18), 11–12 (2006)
Mailloux, R., Santarelli, S., Roberts, T., Luu, D.: Irregular polyomino-shaped subarrays for space-based active arrays. Int. J. Antennas Propag. 2009 (2009)
Mollin, R.: An Introduction to Cryptography. Discrete Mathematics and Its Applications. Chapman & Hall, London (2007)
Moore, C., Robson, J.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26, 573–590 (2001)
Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Books on Mathematics. Dover Publications, NY (1998)
Parker, D., Zimmermann, D.: Phased arrays-part I: theory and architectures. IEEE Trans. Microw. Theory 50(13), 678–687 (2002)
Reid, M.: Tiling with similar polyominoes. J. Recreat. Math. 31(1), 15–24 (2002)
Ryan, D., & Foster, B.: An integer programming approach to scheduling. In: Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, pp. 269–280 (1981)
Shannon, C.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423 (1948)
Simonyi, G.: Graph entropy: a survey. Comb. Optim. 20, 399–441 (1995)
Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1), 111–128 (2000)
Vanderbeck, F.: Branching in branch-and-price: a generic scheme. Math. Program. 130, 249–294 (2011)
Wang, P.: 2 algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 31(3), 573–586 (1983)
Acknowledgments
The first two authors were supported by AFOSR Grant FA9550-08-1-0268. The third author was supported by AFOSR Grant FA9550-12-1-0105. The authors thank Dr. Osman Y. Özaltın and Gabriel L. Zenarosa for their valuable comments on the earlier draft of the paper and Dr. Scott Santarelli for his assistance with antenna simulation software. The first two authors also acknowledge Dr. Arje Nachman and Dr. Donald W. Hearn from AFOSR for introducing them to the considered application. Finally, the authors thank the reviewers and the AE for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Robert J. Mailloux: USAF Senior Scientist, Retired.
Appendix: Pseudocodes of the algorithms
Appendix: Pseudocodes of the algorithms
Proposition 9
Algorithm 1 returns a valid lower bound.
Proof
Proof. To show its correctness, i.e., that it returns a feasible solution, assume \(j'\) is the last subset considered by Algorithm 1. For \(j'\), \(\hat{y}_i = \frac{r_{j}}{\ell } \le \frac{r_{j'}}{\ell }\) for every \(i\in I^-\) as value of \(\hat{y}_i\) must have been set by a previous subset j and \(r_{j} \le r_{j'}\). Therefore, \(\sum _{i\in \hat{f}_{j'}}\hat{y}_i \le r_{j'}\). This is true for all \(0\le j\le j'\). If \(j'<|\bar{N}|-1\), then \(L=m_1\) and \(\sum _{i\in \hat{f}_{j}}\hat{y}_i \le r_{j}\) for all \( j > j'\). \(\square \)
Rights and permissions
About this article
Cite this article
Karademir, S., Prokopyev, O.A. & Mailloux, R.J. Irregular polyomino tiling via integer programming with application in phased array antenna design. J Glob Optim 65, 137–173 (2016). https://doi.org/10.1007/s10898-015-0354-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-015-0354-8