next up previous
Next: Compilation Up: Example: Implementing TSP Previous: TSP's extend_cost

Correctness, delta_correctness, and extend_correctness

For TSP on complete graphs, all solutions are correct (feasible). For problems such as Graph Coloring are may be incorrect solutions, which must be penalized in some way. Our current implementation of Graph Coloring penalizes incorrect solutions (improper colorings) inside the cost function. Therefore, correctness, delta_correctness, extend_correctness need not be defined. Users have the option of defining a measure of correctness separately from the cost function and rely on DISCROPT's ability to combine them. In such cases, correctness, delta_correctness, and extend_correctness are defined in a similar fashion as cost, delta_cost, and extend_cost.

When these functions are not defined, we must set:

const bool ObjectiveFunction::correctness_defined = false;
double ObjectiveFunction::correctness(CircularPermutation & sol)
{
  return 0;
}
double ObjectiveFunction::delta_correctness(CircularPermutation & sol,
                                        const mutation_element &mut_el)
{
  return 0;
}
double ObjectiveFunction::extend_correctness(CircularPermutation & sol,
	                                   const mutation_element &mut_el)
{
  return 0;
}



Vinhthuy Phan 2003-05-15