Optimization over permutation? Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > 0$. I would like to optimize $f$ over $\Pi$, i.e., $\Pi^*=\arg\min_{\Pi\in Perm(n)}f(X,\Pi)$. Is there any good approximate algorithm for this?
 A: 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.
A: Simulated annealing is a good answer, as given by Kjetil B Halvorsen.  You can also try genetic algorithms to mix and cross-over multiple tries at different permutations.
Say that $\Pi_a$ and $\Pi_b$ are two permutations in your permutation space.  If the function $f$ is not a black box, or if it is a black box which you are allowed to use as an oracle, find the value $f_a$ for $\Pi_a$ and $f_a$ for $\Pi_b$, or for a larger population of permutations.  Take two or three of the highest scoring permutations based on the values of $f(X,\Pi_j)$ and use a genetic algorithm to cross-over between these two permutations.
Or take the single highest scoring permutation and then internally permute a short region of the permutation and recalculate $f$.  Iterate as necessary.  This presumes that $f$ if smoothly continuous and that you can use a hill-climbing style of approach to find local maxima or local minima, whichever you need in your case.
A: At lerast, simulated annealing is simple to program for your problem, so you could just try it ...
