Little's Algorithm for the Resolution of the TSP

Imed Chihi
August 1997

[!] I'VE LOST THE SOURCE CODE, I'LL PUT IT BACK AS SOON AS I FIND A COPY.

Overview


This is an implementation of the Little's algorithm to solve the Traveler Salesman Problem. The Little's algorithm is a branch and bound approach. The heuristic used to select the branch to be developed in the tree relies in a concept that tries to estimate how much we will gain by selecting it.
The Little algorithm gives an exact solution to the TSP problem, that's why it is very resource-consuming. Indeed, it proceedes by building a tree with a matrix at each node. The same C code source was compiled twice on the same i486 computer with two operating systems: Windows 95 and Linux kernel 1.3. Under Windows we used the Borland C compiler version 3.1, we achieved a maximal of 16-node problem size, beyond 16 nodes, the systems hangs strangely. Under Linux we used the GNU C compiler and we achieved up to 67 nodes. We could do better simply by addind swap space. The source code is well commented. It is fairly stable and might crash under very heavy loads.

Last updated 2003-12-04.