Bellman–Held–Karp Algorithm for TSP containing restrictions

Question

I am modifying the Bellman–Held–Karp Algorithm for TSP, using dynamic programming. In this case, the difference of the classical Bellman-Held-Karp algorithm is that some cities must be visited before others, but I need to conserve the minimization path cost. Before implementing it in a programming language, I am modifying the pseudocode, with finality to solve and prove the solution. I am trying with an example something like as cities ordered by [1,2,3,4,5..n], in a complete graph, and starting by first city (first index), and the 5th cities cannot appear before the second, for example. I am using as base this pseudocode:

function algorithm TSP (G, n) is
    for k := 2 to n do
        C({k}, k) := d1,k
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, . . . , n}, |S| = s do
            for all k ∈ S do
                C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]
            end for
        end for
    end for

    opt := mink≠1 [C({2, 3, . . . , n}, k) + dk, 1]
    return (opt)
end function

I am thinking of saving the maximum city index in the list (in the recurrence), to ensure that it will never be higher, but I am not sure if this approach is correct.

minm≠k,m∈S [C(S\{k}, m) + dm,k] + max(S\{k + i < 4})

Is corret this approach? Can someone help me?

user_47984 · Answer

I don't understand your second code snippet, or what you mean by recording the "maximum city index" (won't this always be the same for a given set S?), but in any case: In my experience, trying to recording "side information" alongside DP solutions almost always turns out to cause subtle bugs, usually because it assumes some kind of solution uniqueness that is in fact absent. E.g., there could be two different optimal-length paths that visit some set S of vertices and end at m -- so which one is the side information actually talking about?

A different approach allows arbitrary precedence constraints. Let succ(v) be the set of cities that must appear after city v. Change

C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]

to

if succ(k) ∩ S\{k} = ∅:
    C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k]
else
    C(S, k) = INF

The idea is simply to heavily penalise any path in which some successor of v appears before v, ensuring that it will never be selected as part of an optimal solution.

Bellman–Held–Karp Algorithm for TSP containing restrictions

1 Answers