# Welcome!

#### 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.

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.

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

#### Presentations

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

#### Reports

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