# 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?

-
You need to say something about $f$. If it is just a black box, you can't even look at al its values in less than $n!$ time. If there is a linear function $\lambda$ such that $f(\Pi) = \lambda(\Pi_1, \Pi_2, \ldots, \Pi_n)$, this is the assignment problem en.wikipedia.org/wiki/Assignment_problem and there is an excellent algorithm. If there is a linear function $\mu$ such that $f(\Pi) = \sum \mu(\Pi_{i}, \Pi_{i+1})$, this is the Traveling Salesman problem and there is no good algorithm. Other situations, of course, may have intermediate difficulties. – David Speyer May 11 '10 at 12:15
"linear function $\mu$" should simply read "function $\mu$". – David Speyer May 11 '10 at 18:29
The function that I am looking at is more like a negative log joint probability coming from a Bayesian network. I wonder if there is any greedy algorithm could possibly give us somewhat non-trivial approximation. But the points you mentioned are pretty interesting. – pacificmoth May 12 '10 at 19:53
as David points out, you need more structure on the problem. It's often possible to relax the permutation constraint to a doubly stochastic constraint (giving a linear relaxation) or even to an orthogonality constraint (yielding a minimization over SO(n)). Depending on f(), these problems can sometimes be related to the original problem. – Suresh Venkat May 13 '10 at 2:53

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.

-

At lerast, simulated annealing is simple to program for your problem, so you could just try it ...

-

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.

-
George Bernard Shaw once quipped that a second marriage was the triumph of optimimization over permutation. – Will Jagy Sep 4 '10 at 4:13
@will jagy: So that means Elizabeth Taylor, and others of her ilk, were striving to continually optimize over 7+ iterations as they were certain that they had been stuck in a local maximum (or minimum, depending on whose point of view you consider)? – sleepless in beantown Sep 4 '10 at 4:22
Yes, I think that is the inevitable conclusion. You can't argue with Shaw.  I found the best version in an Australian website for woodworkers. Go figure.  woodworkforums.com/f17/divorce-54547 – Will Jagy Sep 4 '10 at 4:28
Oh, one of your expressions between dollar signs is \f(X,\Pi_j) which does not work on my screen as \f does not mean anything to Latex – Will Jagy Sep 4 '10 at 4:33
@will, Thanks! I got carried away typing the backslashes in front of the capital Pi's and inserted a few extra accidentally. Edited and fixed. – sleepless in beantown Sep 4 '10 at 4:53