Differences

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

@@ 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]]).

Welcome!

Differences

Page Tools