This shows you the differences between two versions of the page.
— |
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]]). | ||