Welcome!

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

• 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!

• 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 a conclusion about your ideas based on the experiments.

• Date: January 10 and 17, 2017.
  • 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.

• 4-8 A4 pages.
• Include your name, student id, and e-mail.
• Strongly recommended using 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 “Drop Box” on the class portal Panda.
  • Late submissions:
    • Late submissions will not be accepted. By not submitting a report you forfeit 50% of your grade.

As of 2020, this part of the class will be taught by Assoc. Prof. Kazuya Haraguchi. Please check his website for materials.

2016