Integer linear programming models for the problem of covering a polygonal region by rectangles
Authors: G. Scheithauer, Y. G. Stoyan, T. Romanova,
Radioelectronics & Informatics 45/2 (2009) 4-13 (Preprint MATH-NM-07-2009)
The aim of the paper is to develop integer linear programming (ILP) models for the problem of covering a polygonal region by rectangles. We formulate a Beasley-type model in which the number of variables depends on the size parameters. Another ILP model is proposed which has $O(n^2 \max\{m,n\})$ variables where $m$ is the number of edges of the target set and $n$ is the number of given rectangles. In particular we consider the case where the polygonal region is convex. Extensions are also discussed where we allow the polygonal region to be a union of a finite number of convex subsets.
Preprint version: PDF
Back