A branching solver for the TSP

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

Note

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

  • Number n of cities between 6 and 10 in increments of 1, and up to 32, in increments of 2;
  • Probability p of an edge between 0.3 and 1.0, in increments of 0.1
    • Treat the number 32676 as no edge or infinity;
  • For each set of parameters n and p, there are 10 random instances.

Your task is to conduct experiments with your original branching/bounding rules.

  • Use the sparseness of an instance (the fact that there are few edges) to your advantage!
  • Not all instances have a feasible solution! Modify the program to report this.
  • Report your time results averaged over 10 instances.
  • Try to solve as large instances as possible!

Final Presentations/Reports

Common points

  • Prepare your presentations/reports in such a way that anyone seeing them for the first time can understand the contents. Mainly, do not jump to your results.
    • Write a nice introduction where you explain the problem you work on.
    • Cover some applications.
    • Explain possible solution methods (do not limit yourself to those covered in class).
    • Explain your choice of solution method.
      • Focus most on your improvement idea.
    • Report experiments.
      • Follow good practice, identify your tables and charts with appropriate captions, do not forget to label your axes.
    • Give conclusion about your ideas based on the experiments.

Presentations

  • Date: TBD.
    • Completely in English.
    • Presentation time: 15 min (10 min presentations, and 5 min Q&A). Try not to go over your 10 min of presentation.
    • Bring your own computer, and if necessary, a VGA adapter; or, bring a USB or an SD card to present using my computer.

Reports

  • 4-8 A4 pages.
  • Include your name, student id, and e-mail.
  • Strongly recommended to use English. Small grammar/spelling mistakes will not influence your grade, as long as you get your point across.
  • Deadline: Before your scheduled presentation class.
  • Submission:
    • Through the class web-page on Panda.
    • Late submissions:
      • Late submissions will not be accepted. By not submitting a report you forfeit 50% of your grade.

Past years