TSP's extend_cost

One of the powerful heuristics we use is based on the traditional greedy method, by which a solution is constructed incrementally from most-promising elements selected from a pool of possible extensions. We generalize this abstract greedy strategy to a local-search greedy method, by viewing each possible extension as a neighboring solution so that the act of extending a solution is considered as moving from one solution to its most promising neighbor.

Extend_cost takes a solution and a mutation and returns the cost of the extension from the solution to an extending neighbor obtained by extending the given solution. Extension is defined by inserting an element $e$ into a position $p$; mutation_element::first indicates a position $p$, and mutation_element::second indicates the element to be inserted into $p$. The meaning of this extension ($p$ and $e$) depends on the solution representation:

1. Circular permutation, permutation - There are $n+1$ possible positions for $p$. If the solution is $s[s_1 \cdots s_{j-1} s_j \cdots s_n]$, then inserting an element $e$ into a position $p$ creates the solution: $s[s_1 \cdots s_{p-1}\, e s_p \cdots s_n ]$.

2. Subset - There are two possible positions for $p$: 0 and 1, which means either inserting the element $e$ into the subset solution or not inserting $e$ into the subset solution. In either case, $e$ is inserted into the set that contains the subset solution.

3. Partition - If $m$ is the number of parts in the given partition, then there are $m+1$ possible positions for $p$. Inserting $e$ into one of the parts creates a new extension. When $p = m+1$, $e$ is inserted into a new part.

For TSP, extend_cost is:

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

In DISCROPT, it is written as:

double ObjectiveFunction::extend_cost(CircularPermutation & sol,
                                      const mutation_element &mut_el)
{
  double weight=0;
  int pos = mut_el.first, prev_pos = sol.previous_index(mut_el.first);
  int new_ele = mut_el.second;

  if(pos > sol.last_index()) pos = sol.first_index();

  weight = search_space->edge_weight(sol[prev_pos], new_ele) 
    + search_space->edge_weight(new_ele, sol[pos]) 
    - search_space->edge_weight(sol[prev_pos], sol[pos]);

  return weight;
}

Delta_extend must be defined so that

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

where $ns$ is an extension of $s$ obtained by inserting element $m_e$ into the position $m_p$ of $s$.