Theory - Traveling Salesman Problem

Application

The traveling salesman problem, like many nonlinear optimization problems with a large number of parameters, is typically solved using an approach that utilizes randomness, rewards improved optimization, and allows for diversity in possible solutions to reduce the chance of becoming stuck in a local minimum.

Algorithm

The model used in this case is a simulated annealing model, in which perturbations are made to the salesman's path. Perturbations that improve the optimization are automatically accepted, and perturbations that do not improve the optimization are sometimes accepted at early stages in the optimization, but less often accepted in later stages of the optimization. This can be thought of as a "cooling" process, and indeed the parameter used to determine whether or not to accept a perturbation that does not improve the optimization is called the temperature. If one thinks of the optimization process as a simplex rolling downward, a higher temperature would occasionally "shake things up", allowing a simplex to pop out of a local minimum and possibly find a better global minimum.

Perturbations in this model can take one of many forms--a random rearrangement of all cities, a random rearrangement of a few contiguous cities, a swap of two random cities, a reversal of some number of contiguous cities--and the optimization parameter in the model is the total length of the salesman's trip.

The parallelization of this problem is not entirely trivial, as having 10 processes attempt 10 trials in parallel is not equivalent to having 1 process calculate 100 trials. Each trial has the potential to improve the solution, but if all processes improve by the same amount, having more processes participate may or may not be helpful. The implementation that has been used in this problem has P processes attempting N trials and then comparing to see who has the best solution. Each process restarts using the best current known solution, and this process is repeated M times.

Architecture

This traveling salesman model is designed to run on a UNIX machine from a command line, with X-Windows used for visualization. Parallelization of the code has been done using MPI.