I was thinking about coding questions, and how you would write a coding question that tested peoples’ ability to explore algorithms in areas they weren’t likely to be that familiar with without necessarily being able to come up with optimal solutions.

I mulled over this a bit and came up with one which is entirely too evil to use. However I rather feel like I’m going to have to try to implement it anyway because it’s going to bug me. I figured I would inflict this on the rest of you, because misery loves company.

The problem is this:

You are given a non-negative symmetric \(n \times n\) matrix \(A\) with \(A_{ii} = 0\), with real numbers represented as double precision. This is your potential matrix.

Find an assignment of coordinates \(x_1, \ldots, x_n \in [0, 1]\) that has a low value for the energy function \(E = \sum\limits_{1 \leq i < j \leq n} \frac{A_{ij}}{|x_i – x_j|}\). You are not required to minimize it, but if you can that would be lovely.

Some initial thoughts on how one might solve it:

1. Any optimal solution for a non-zero \(A\) assigns at least one point to 0 and at least one point to 1.
2. For any given starting position there is a relatively straightforward gradient descent algorithm to find a local minimum
3. If \(A_{ij} > 0\) for all \(i \neq j\) then there are at least \(n!\) local minima.
4. If you’ve placed \(k\) items and you want to place a \(k + 1th\), as long as it has a non-zero coordinate in \(A\) with at least one of the items you’ve placed so far there is a unique place to put the k+1th item (though finding this is O(k)). This probably makes a greedy algorithm quite productive for smallish \(n\).
5. If the graph with edges \(\{ \{i, j\} : A_{ij} \neq 0\}\)  is not connected you can run the problem separately on each component and merge the results, because they don’t affect each-other.
6. Some form of e.g. simulated annealing with the mutation operator being to swap pairs of elements then run a local optimisation would probably be quite productive.

As an additional comment: Trying to do combinatorial optimisation on permutations of indices is an exercise in frustration. Believe me, I know. This problem may prove more annoying than it’s worth.