Solver hangs

I don't see this that often: a solver that completely hangs. 

It keeps using CPU cycles.

Without knowing the solver's internals, my (brave) guess is an infinite loop. Note to myself: in production code, loops should always be protected (simply by an iteration count, or maybe a timer). I guess some exceptions are the operating system and a GUI event loop.

Rectilinear Clustering: area or perimeter?

In the previous post, I discussed covering \(k\) of \(n\) 2d points with the smallest possible rectangle. Minimizing the area yields a nonconvex quadratic objective. Solving these models requires global solvers. If we use the perimeter as a measure of size, the problem becomes linear. An example suggested that the solutions of these two approaches are similar. It certainly looked that way:

The picture shows the smallest rectangle containing \(k=25\) of a hundred random points. Minimizing either the area or the perimeter yields very similar rectangles. This comes from [1], where I noted that in this case the quadratic model (min area) and the linear model (min perimeter) yield similar solutions, but this is not guaranteed in general.

Here I discuss a different, but related problem: cover all points with \(k\) rectangles of minimum size. This problem is a well-known clustering problem that uses Manhattan or \(L1\) distances instead of the more traditional Euclidean distance. Again, we can choose area- or perimeter-based objectives. It is interesting to see the difference.