Differences

This shows you the differences between two versions of the page.

Link to this comparison view

classes:advanced_or:2016 [2017/02/04 23:02] (current)
shurbevski created
Line 1: Line 1:
 +=== A branching solver for the TSP ===
 +
 +Please use the {{classes:​advanced_or:​tsp_b.cpp.zip|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 {{classes:​advanced_or:​tsp_instances.zip|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 edgeweights given in FULL_MATRIX format.
 +\\ Check the [[http://​www.iwr.uni-heidelberg.de/​groups/​comopt/​software/​TSPLIB95/​|TSPLIB homepage]] for more info.
 +
 +Try to compare the program with the state-of-the-art [[http://​www.math.uwaterloo.ca/​tsp/​concorde.html|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. 
 +
 +<color red>NEW! </​color>​
 +\\ Check out the new {{classes:​advanced_or:​new_tsp_instances.zip|set of instances}}.
 +\\ 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 instance as possible!
 +
 +==== Final Presentations/​Reports ====
 +
 +=== Common points ===
 +  * Prepare you 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.
 +      * <color #​7092be>​Focus most on your improvement idea.</​color>​
 +    * 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 ===
 +  * Presentations will be held on January 19th and January 26th.
 +    * Completely in English.
 +    * Presentation time: 8 min (7 min presentations,​ and 1 min Q&A). Try not to go over your 7 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 through.
 +  * Deadline: Feb 3rd 2017, 17:00.
 +  * Submission:
 +    * Place a hard copy in the provided box on the door of Room 312, Research Building 8 ([[:​contact|my office]]).