Packing circles in a rectangle: a MIQCP model

An interesting problem was posed here. Given a set of circles (with given radius) try to cover as much area of a rectangle. Here the circles represent sensors.



The circles may look more like ellipses as the aspect ratio of the plot is not one (the plot is too wide).

It looks very difficult to me to develop a model that minimizes the uncovered (white) area in the above picture. We are dealing with overlapping circles and and circles that cover areas outside the rectangle.

However if we superimpose over the rectangle a grid with points, and try to minimize the uncovered points we may have a chance. In the model below we try to solve this by maximizing the number of points covered by at least one sensor:



Basically we model two implications and an objective:


For points inside circle k we don't impose anything, but leave it to the objective to drive things in the right direction. We repeat this trick in the second implication.

As this is a convex MIQCP, we can use some commercial solvers like Cplex and Gurobi. For large problems however this thing turns out to be not so easy to solve. The picture at the top of this post represents the optimal solution for the model with the small random data set of just four sensors.

Update

As noted in the comments, it may be better to exclude the points on the boundary of the rectangle. The result is:

Another approach would give those points a weight of 0.5: