oc.optimization control - Optimization over permutation?

It may be the case that simulated annealing and genetic algorithms are relatively complicated to understand, bound and implement in this instance.

Instead, a very easy starting point would be a simple hill-climbing algorithm.

Start with an arbitrary (or better, random) initial permutation $pi$.

The set of moves is the set $M$ of permutations that you can reach by transposing two elements of the permutation.

While there is a move that decreases $f$,

• Make the move to reach a new current permutation.




• Compute the new set of moves (or rather, their profits $f(pi) - f(pi')$ for a move reaching $pi'$).

This will get you to a local minimum at a cost of $O(n^2)cdot C(n)$, per move, where $C(n)$ is the cost of calculating $f(pi)$ for a permutation of $[n]$.

Extremely simple and probably not too costly as a first step. You may be able to prove some sort of worst case bound between a local optimum and a global optimum.