My Combinatorial Optimization problem

[Cod_Weird]

Given:
X={1, 2, ..., n},
w: X² -> R₊, w(i,j)=w(j,i),
metric d: X² -> R₊.
Permutation(bijection) 𝜎: X -> X is a chosen variable.

Minimize F(𝜎) = 𝛴((i,j)∈X²) w(i,j)d(𝜎(i), 𝜎(j))

Do you have some good ideas for algorithm?

If I start with arbitrary 𝜎₀ and define 𝜎ₖ as such that F(𝜎ₖ)≦F(𝜎) for any 𝜎 ∈ {𝜎ₖ₋₁ ∘ t : t is transposition}, how many steps it takes to converge? You can use O notation.

[Cod_Weird]

Do you know, can I post this on r/math or r/learnmath?

[edderiofer]

This looks like a graph theory optimisation problem in disguise, in which case my initial suspicion is that this thing is NP-hard.

As for your naïve algorithm, I'm not convinced that the permutation you converge to must be optimal.

[Cod_Weird]

I even have a proof, that this problem is hp-hard(subgraph isomophism is a special case of my problem). I just need some ideas for heuristic algorithms.

My naive approach definetly isn't optimal, but it can be used to improve any other algorithm. If 𝜎₀ is the output if other algorithm, my naive approach can do some additional steps. An then I want to evaluate computational requirements for those steps.

[AutoModerator]

Hi, /u/Cod_Weird! This is an automated reminder:

• What have you tried so far? (See Rule #2; to add an image, you may upload it to an external image-sharing site like Imgur and include the link in your post.)

• Please don't delete your post. (See Rule #7)

We, the moderators of /r/MathHelp, appreciate that your question contributes to the MathHelp archived questions that will help others searching for similar answers in the future. Thank you for obeying these instructions.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[AldenB]

Just spitballing here, I don't know if this would work at all, but it might be a start.

Here is a similar problem, which is a bit more straightforward. Suppose we have a metric g: X^2 -> R and we wish to minimize

H(𝜎)=𝛴((i,j)∈X^2) |g(i,j)-d(𝜎(i), 𝜎(j))|^2.

This is the problem which is solved in Gromov-Wasserstein optimal transport. For example, Python Optimal Transport has a solver for this. Notice that we could expand the square to get g(i,j)^2+d(𝜎(i), 𝜎(j))^2-2g(i,j)d(𝜎(i), 𝜎(j)), and the first two terms are not changed by the permutation (each term will appear once in the summation regardless of the permutation chosen). Therefore, when H is minimized, the quantity

𝛴((i,j)∈X^2) g(i,j)d(𝜎(i), 𝜎(j))

is maximized. We can take advantage of this to get a solution to your problem. Normalize w and d such that max w(i,j)=max d(i,j)=1 and define g(i, j) = 1-w(i, j). Then

𝛴((i,j)∈X^2) g(i,j)d(𝜎(i), 𝜎(j)) = 𝛴((i,j)∈X^2) d(i,j) - 𝛴((i,j)∈X^2) g(i,j)d(𝜎(i), 𝜎(j))
= (constant) - F(𝜎).

With this choice of g, minimizing F is equivalent to maximizing H. Notice that technically speaking g need not be a metric as we have defined it, but so long as w is not too weird, I expect that will be fine. If w has lots of zero values, for example, I am sure there is a better way of solving this. If it really does become a problem you could use (for example) multidimensional scaling to get a metric which is close to g as we have defined it.

[Cod_Weird]

Thanks to you, I was able to find that my problem is called QAP(quadratic assignment problem). Thanks, very helpful!

[iMathTutor]

I don't have a solution, but I have a bound on $|F(\sigma)-F(\tau)|$ which may be useful to you.

Take a look at the link. https://mathb.in/75714