How to order objects to minimize non-adjacency cost

Question

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent in the array. Is there an algorithm that orders the object array to minimize the total cost?

The costs will change from time to time, so I'd like to be able to apply the algorithm iteratively. It doesn't have to produce an optimal solution, but should converge to one if the costs remain constant over enough iterations. Practically, I will have somewhere around 1,000,000 objects, and each object will be a member of about 5 pairs.

Here is what I have tried:

1. Combine pairs that refer to the same two objects by summing their cost.
2. Each iteration, find a random pair whose cost changed. If no costs changed, take a random pair.
3. For each of the two objects from the pair as obj1:
   1. Set obj2 equal to the other object.
   2. For each of the two objects touching obj1 as obj3:
      1. Calculate the cost difference of swapping obj2 and obj3.
      2. If it is less than zero, apply the swap and return.

I like my algorithm but it's pretty simple and I feel like it would fall on its face in select circumstances. Is there a better algorithm or some terminology I can google for?

Answer 1

Your problem is just the problem of finding a maximum-weight Hamiltonian path in a weighted graph.

A candidate way of ordering objects in your array corresponds to a Hamiltonian path. The total weight of that Hamiltonian path (the sum of the weights on the edges in the path) is exactly the sum of the "non-adjacency costs" you don't pay. Minimizing the sum of the "non-adjacency costs" you do pay is equivalent to maximizing the sum of the "non-adjacency costs" you don't pay.

Unfortunately, this problem is NP-hard, so you should start looking for approximation algorithms or heuristics or special cases. For instance, there may be some special kinds of graphs (say, bounded treewidth or bounded clique-width) for which this problem might be solvable in polynomial time.

See also https://en.wikipedia.org/wiki/Hamiltonian_path_problem and https://en.wikipedia.org/wiki/Longest_path_problem.

You might also try looking at simulated annealing, which is often a good candidate approach to explore for these kinds of problems, and is in some ways a generalization of the sort of algorithm that you mention in your question.