Another quadratic problem that has some interesting features – this is an old favorite of mine. The problem is stated as follows: a patriarch has *n* sons and wants to build them each a house on his estate such that the minimum distance between them is maximized. We assume here the parents plot is simply [0,1]x[0,1] and high fertility led to *n*=75 brothers.

When we random place the points we get a small minimum distance: 0.0088. The two orange points almost overlap.

When forming the objective function we can do two immediate tricks:

- We don’t need to compare all points
*i,j*with each other twice. We can limit the distance calculations to the lower triangular part, i.e. were*i > j*. - We can drop the
**sqrt**in the distance calculation as this is a monotonic function. - The default GAMS all-zero starting point is very bad: all gradients are zero. E.g. conopt will just stay at that point: it does not move an inch. Better is to use the above random configuration as initial point. From the results we see this is actually not a bad starting point.

There are two different objectives we can use. The first objective is a nice, compact single objective function that is unfortunately non-differentiable. The second formulation leads to a set of upper limits on **mindist** (we are maximizing **mindist** so we automatically find the correct one; note that **mindist** represents the **squared** minimum distance). The set *lt(i,j)* has *0.5(n ^{2}–n)*=2775 elements, so we have 2775 inequalities in the second case.

Typically local NLP solvers like the second form better. E.g. with Conopt:

S O L V E S U M M A R Y MODEL m1 OBJECTIVE mindist **** SOLVER STATUS 4 Terminated By Solver |

S O L V E S U M M A R Y MODEL m2 OBJECTIVE mindist **** SOLVER STATUS 1 Normal Completion |

The second objective is much better although the model is much bigger, and we get a minimum distance of 0.1302. As you can see here, problem size is not all that matters when solving optimization problems. The brothers are now located as follows:

The orange points indicates where we observe the minimum distance. This starts to look like a grid we would expect. This also explains why we see an increase in the use of nonlinear programming in packing applications.

Next: towards global solutions.

#### Update: 3d version

We can generalize to 3d as follows. The plots are somewhat difficult to understand.

Note: the red colors are related to the y-coordinate of the point.

Random thought, how does this the problem behave in higher dimensions, e.g. 3D?

ReplyDelete