The traveling salesman problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP hard problems in combinatorial optimization There is no know polynomial time solution for a TSP. Monte Carlo methods (or Monte Carlo experiments) are a class of computational algorithms that rely on repeated random sampling to compute their results. These algorithms never guarantee a 100% optimal solution. We are using the Monte Carlo algorithm to find a solution that is guaranteed to be close to the optimal solution. Sine the computation of a TSP is beyond the capability of a day-to-day use system we distribute the work of finding the optimal path using the MapReduce technology from Google. We run the TSP on a cluster using Apache Hadoop, a framework from Apache implemented in java which helps in performing MapReduce tasks.
MapReduce is used for distributed computation framework which is used to process very large sets of data that and stored in many computers. Due to its superior architecture, some of the most common issues faced in distributed architecture like splitting input data and placing it over various systems, scheduling and executing tasks on various nodes, coordination of tasks running at different note, dealing with network failures are handled perfectly. MapReduce deals with its input in terms of key value pairs, which are generated from an input file by user configurable rules. MapReduce uses a very simple programming model, which in its most abstract form requires its user to write only two functions, map and reduce. In MapReduce, a reduce is performed over all outputs of map with the same key. Reduce function will take in a key and a list of values, and output a key value pair.
Parallelizing Tabu Search
Since we can summarize Tabu search as an algorithm which evaluates a combination of possible moves, and picking the good one. This search can be easily translated in to MapReduce
- Map - Each mapper evaluate a different move and returns a value which indicates how much objective value can be changed.
- Reduce - Values returned by different mappers are compared and logic will be applied which decreases the objective value the most.
- Repeat the process
This approach have a many drawbacks. Even though start up time of MapReduce is very small, using MapReduce multiple times for effective use of Tabu search, would consume a lot of time. So the objective of this project is to reduce the number of MapReduce iterations solution can be modified as follows
- Map - Let each mapper pick a random starting solution, and run Tabu search on each machine. After execution, map will return the best solution found during the process.
- Reduce - Compare results returned by all Mappers, and get the solution with lowest objective.