Ant colony optimization can be applied to the traveling salesman problem on n cities as follows.
Initially all the ants of the colony are in City 1.
In each iteration, each ant crawls from its current location i to city j with probability proportional to uij/dij, where uij is the density of accumulated pheromone deposit on the trail from i to j, and dij is the distance from i to j.
Each ant deposits pheromone at a constant rate while crawling, and a certain fraction of the pheromone evaporates between each iteration and the next.
Each ant remembers where it has been and does not visit the same city twice until all cities have been visited.
After returning to City 1, the ants forget everything and start over again.
When the process terminates, the shortest tour found by an ant is selected.
Show how this algorithm can be understood as enumerating problem restrictions.
How can relaxation bounding be introduced into the algorithm?