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?

  • 19
    $\begingroup$ 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. $\endgroup$ – David E Speyer May 11 '10 at 12:15
  • $\begingroup$ "linear function $\mu$" should simply read "function $\mu$". $\endgroup$ – David E Speyer May 11 '10 at 18:29
  • $\begingroup$ 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. $\endgroup$ – pacificmoth May 12 '10 at 19:53
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ George Bernard Shaw once quipped that a second marriage was the triumph of optimimization over permutation. $\endgroup$ – Will Jagy Sep 4 '10 at 4:13
  • $\begingroup$ @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)? $\endgroup$ – sleepless in beantown Sep 4 '10 at 4:22
  • $\begingroup$ 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 $\endgroup$ – Will Jagy Sep 4 '10 at 4:28
  • $\begingroup$ 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 $\endgroup$ – Will Jagy Sep 4 '10 at 4:33
  • $\begingroup$ @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. $\endgroup$ – sleepless in beantown Sep 4 '10 at 4:53

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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.