TSP's delta_cost

Local search heuristics such as simulated annealing and hill climb move from one solution to a neighboring solution to find the best one. Instead of recomputing the cost, we can use delta_cost to save a factor of O$(n)$ computation.

Delta_costs takes a solution and a mutation and returns the cost of the change a solution to the neighboring solution obtained by mutating the given solution. Different solution representations have different definitions of mutation (implementation details are in operator.cpp):

1. Circular permutation, permutation - a mutation means exchanging two random indices. The indices are stored in mutation_element::first and mutation_element::second.

   Therefore, a neighbor of $s$ has the same permutation as $s$ except at two indices.

   The difference is that a circular_permutation is equivalent (i.e. same objective cost) to all of its cyclic orders; the search space is narrower.

2. Subset - a mutation means taking a random item and reversing its position: if the randomly selected element is in the subset solution, it is removed from the subset; conversely, if the randomly selected is not in the subset solution, it is placed in the solution. This random element is stored in mutation_element::first.

   Therefore, a neighbor of $s$ has the same subset as $s$ except one element whose position is flipped.

3. Partition - a mutation means moving a random element (stored in mutation_element::first) to different random parts (stored in mutation_element::second).

   Therefore, A neighbor of $s$, has the same partition as $s$ except an element is moved to another (possibly new) part.

Relevant files to look at are: combinatorial_solution.h, (circular_)permutation.h, subset.h, partition.h, operator.cpp, basic_types.h.

For TSP, any two neighboring circular permutations differ by an exchange of two indices. In other words, if $s$ and $\delta s$ are neighbors, then they are exactly the same except at two indices, say $i$ and $j$, where $s[i] = \delta s[j]$ and $s[j] = \delta s[i]$. Suppose $\vert i-j\vert \ne 1$, then we can define delta_cost $(s, \delta s)$ as:

$$- d(s_{\pi(i-1)}, s_{\pi(i)}) - d(s_{\pi(i)}, s_{\pi(i+1)}) - d(s_{\pi(j-1)}, s_{\pi(j)}) - d(s_{\pi(j)}, s_{\pi(j+1)})$$

$$+ d(s_{\pi(i-1)}, s_{\pi(j)}) + d(s_{\pi(j)}, s_{\pi(i+1)}) + d(s_{\pi(j-1)}, s_{\pi(i)}) + d(s_{\pi(i)}, s_{\pi(j+1)})$$

We also need to address the special case when $\vert i-j\vert=1$. In DISCROPT, it is written as follows (details omitted):

double ObjectiveFunction::delta_cost(CircularPermutation & sol,
                                     const mutation_element &mut_el)
{
  int i = mut_el.first;
  int j = mut_el.second;
  int first = sol[i];
  int before_first = sol[sol.previous_index(i)];
  int after_first = sol[sol.next_index(i)];

  int second = sol[i];
  int after_second = sol[sol.next_index(j)];
  int before_second = sol[sol.previous_index(j)];
  
  double d = 0;
  if((first != before_second) && (second != before_first)){
    d -= search_space->edge_weight(before_first, first);
    d -= search_space->edge_weight(first, after_first);
    d -= search_space->edge_weight(before_second, second);
    d -= search_space->edge_weight(second, after_second);

    d += search_space->edge_weight(before_first, second);
    d += search_space->edge_weight(second, after_first);
    d += search_space->edge_weight(before_second, first);
    d += search_space->edge_weight(first, after_second);
  }
  \\ other cases are omitted...
}

Delta_cost must be defined so that

$$cost(ns) = cost(s) + delta\_cost(s, m)$$

where $ns$ is a neighbor of $s$ obtained by mutating $s$ by $m$.