Packing solar cells on a roof

We consider the problem of finding a suitable placement of solar cells on the roof of a building. Since roofs may be of nonrectangular shape and may have obstacles like chimneys, dormers or windows on them, finding an optimal layout is not a trivial task. Mathematically, this setting belongs to the class of cutting and packing problems, with an additional difficulty in the shape of the disposable roof area: existing approaches do not cover our situation where we deal with nonconvex roofs. We develop a mixed integer linear model for this problem and present an enhanced version of the classical bottom-left heuristic. Examples demonstrate that this new approach considerably improves traditional strategies.