We consider the problem of covering an orthogonal polygon with a
minimum number of axis-parallel rectangles from a computational
point of view. Our integer programming formulation is the first
approach to solve this NP-hard problem
optimally. In experiments it turns out that the linear programming
relaxation is extremely tight. Making use of the dual program, we
propose a new lower bound on the optimum, namely the cardinality of
a fractional stable set. We obtain excellent experimental results
for polygons originating from VLSI design, fax data sheets, black
and white images, and for random instances. We believe that our
proposals have a strong potential to settle the main open problem in
the area: To find a constant factor approximation algorithm for the
rectangle cover problem.
