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=c++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 edge weights 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.
There is a more comprehensive set of instances for you to use for your final report.
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.
As of 2020, this part of the class will be taught by Assoc. Prof. Kazuya Haraguchi. Please check his website for materials.