A GUI for TSP algorithms ======================== This Java programm implements a GUI to be run on a (workplace) PC and which can connect to a remote compute server or distributed cumpute cluster to control the computation of Traveling Salesman Problems (TSP) with several algorithms. TSP finds a shortest path going once through all given points in a plane. In the GUI one can specify the problem size, the TSP algorithm, the degree of parallelism (either for multiple threads or for distributed computation), the maximal number of iterations to be performed and the the remote hostname and port. With this parameters a random problem can be generated and the computation can be started and stopped. During the computation the actual number of iterations performed as well as the actual best computed solution is displayed as graph. In a status window the results of the computations are recorded. Howto ===== Start the GUI with java -jar TSPgui.jar When selecting the option 'standalone' in the fiel menu the sequential and the parallel algorithm can be run directly from the GUI. To use a remote compute server or cluster select the TCP/IP hostname and port and start a daemon / service on this computer with java -jar TSPdaemon.jar With this setup the sequential and parallel algorithms can be run on the comute server. To use the distributed algorithm the same deamon must be launched on all participating distributed computers. This can be done on some clusters via rsh or rexec. The location (hostname) and and port numbers must be recorded in a machine-file. The machine file must be located at the computer with the first (master) deamon. The machine file lists first the master host (the one with which the GUI comunicates) and then all other hosts. If less hosts are listed as degree of parallelism is requested, the hosts are reasigned in a round-robin fashion. On todays (2004/05) computers problem sizes of 12 to 14 are easily computed. To stress a compute server or cluster for a while problem sizes of 20 to 30 are can be used. For best tuning of the java virtual machine on a multi-cpu computer running the daemons use the options -Xms200M -Xmx400M -XX:+AggressiveHeap -XX:+UseParallelGC (adjust memory as desired, jdk 1.4.2) Algorithms ========== The main idea for all algorithms to solve the given TSPs is to enumerate all possible paths which connect the given points (towns). From them the path with the shortest length (~ minimal cost) is selected. Partial paths which already have higher costs than the current best path are discarded (branch and bound algorithm). The sequential algorithm directly solves the problem (using a stack to hold partial paths). The parallel mulithreaded algorithm uses several threads which take partial paths from a (central) work pile and search subtrees in parallel. The distributed algorithm consists of a multithreaded master, which sends partial paths to distributed workers to search subtrees in parallel. Communication is done via TCP/IP using Javas object serialization. Acknowledgements ================ Developed with the help and ideas of the students of BA Mannheim TIT02... Have fun! Heinz Kredel, January 2005, Mannheim Copyright ========= The program can be freely used for educational purposes.