Combinatorial Optimizations Dissertation

The Traveling Salesman Problem (TSP) is well documented as being a hard problem to solve, precisely the optimization form (TSP_OPT versus TSP_DECIDE). Chronicling the thesis development steps of the doctoral dissertation to investigate performance enhancements using divide and conquer approaches and parallel computing approaches, this application provides performance (time and quality of route) analysis of seminal work as well original work developed as part of the dissertation. The exhaustive search is the best-known approach in terms of quality of the results, but runtimes become prohibitive for all but the most trivial instances. The Greedy algorithm is the fastest, simplest, and poorest performing in terms of the quality of the solution. This app demonstrates the time and quality of the greedy heuristic algorithm on a variety of problems (trivial, large realistic, and a couple of pathological sample problems).