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(n2–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.