TSP's Cost

The objective cost of TSP is defined as:

$$d(\pi_{N-1}, \pi_0) + \sum_{i=0}^{N-2} d(\pi_i, \pi_{i+1})$$

In DISCROPT, this is written as:

double ObjectiveFunction::cost(CircularPermutation & sol)
{
  int current, next, size = sol.get_permutation_size();
  double weight=0;

  current = sol.first_index();
  for(int i=0; i<size; i++){
    next = sol.next_index(current);
    weight += search_space->edge_weight(sol[current], sol[next]);
    current = next;
  }
  return weight;
}

A few observations:

• ObjectiveFunction::search_space stores the data structure of the problem instance, in this case a graph. It contains the method edge_weight that gives the weight of an edge. The data structure of search_space must have a public static method called get_size() that returns the size of a solution (of type circular permutation). In TSP, a circular permutation contains all vertices, and therefore get_size() returns the number of vertices in the graph. This function is mandatory as it is used by DISCROPT to generate a random solution.

  In DISCROPT, we use the Graph Template Library (GTL) to provide the graph data structure for TSP. There is no need for GTL if the user provides his own data structure helped to define the objective function.

• The type CircularPermutation has several public methods accessible to users. In this example, the user uses methods get_permutation_size() to get the size of the permutation, and first_index() and next_index() to enumerate the indices of a circular permutation solution.

  For permutation, subset, and partition representations, their elements can still be accessed or enumerated through theindexing mechanism: first_index(), last_index(), next_index(), [ ]. For example, the first element of a circular permutation s is s[s.first_index()].

It must be reminded that DISCROPT minimizes, i.e. if $s_1$ is subjectively better than $s_2$, then cost($s_1$) must be lower than cost($s_2$).