Please use the sample program to develop your own branching and bounding operations.
You need a UNIX environment to compile and run the program (it has been tested on Ubuntu and Windows + Cygwin).
After unpacking the .cpp file, compile the program by typing
g++ -std=gnu++11 -O3 tsp_b.cpp -o tsp_program
You can test the program on some small sample instances.
The program reads a graph from the standard input.
You can redirect the text files as input to the compiled program by typing
tsp_program < tsp_instance
The instances are given in TSPLIB format.
The program only accepts EXPLICIT edgeweights given in FULL_MATRIX format.
Check the TSPLIB homepage for more info.
Try to compare the program with the state-of-the-art Concorde TSP solver.
The present program does not stand much chance, because it uses a very, very simple branching procedure. On small tests, it took negligible time to solve an instance with 5 cities, around 2 seconds for 6 cities, and more than 2 minutes for 7!
Only try the instance with 8 cities at your own risk.
NEW!
Check out the new set of instances.
There are instances for
n
of cities between 6 and 10 in increments of 1, and up to 32, in increments of 2;p
of an edge between 0.3 and 1.0, in increments of 0.132676
as no edge or infinity;n
and p
, there are 10 random instances.Your task is to conduct experiments with your original branching/bounding rules.