Simulated Annealing for the Traveling Salesman Problem

Summary
This application note describes how EnFuzion was used to perform combinatorial optimization. Usually, a long process is involved in tuning a set of parameters for the meta heuristic algorithms applied to solve combinatorial optimization problems. EnFuzion simplified this task by

• coordinating the generation of parameter values
• distributing the work among workstations

What is combinatorial optimization?
Recently, researchers have devised a number of new algorithms (called meta heuristics) for performing combinatorial optimization. Examples of such algorithms are simulated annealing, genetic algorithms, evolutionary computing and tabu search. These algorithms are based on natural phenomena; they can be applied to solve very complex discrete optimization problems.

In this application, researchers explored the tuning of parameters for a program that applies simulated annealing to the Traveling Salesman problem. The algorithm is implemented as a small FORTRAN program (with the SAPARAM.INC include file). Researchers explored two main parameters:

• number of iterations per temperature cycle
• number of times the temperature is raised through re-heating

How did EnFuzion help solve the problem?
Usually, it is necessary to tune a set of parameters for the meta heuristic algorithms used to solve combinatorial optimization problems. Often tuning the parameters is a lengthy process because the code must be run against a range of parameter values, data sets, and random number seeds. EnFuzion simplifies this task by coordinating the generation of parameter values and by distributing the work among workstations.

How was EnFuzion used?
Researchers had to run the program a number of times to obtain an average of the solution cost. In this example, 4000 jobs were run; the jobs were distributed across 31 workstations.

The following plan file was used to control the experiment:

parameter tspfile label "TSP Problem Set" text select anyof
    "berlin52a.tsp" "ch130.tsp" "ch150.tsp" "st70a.tsp" "pr76.tsp"
    "att48.tsp" "bayg29a.tsp" default "st70a.tsp";
parameter runlength label "Run Length" integer
    range from 1000 to 50000 points 80;
parameter seed label "Random Number Seed" integer
    range from 1 to 10 points 10;
parameter trials label "Number of Trials per Run" integer
    range from 1 to 20 points 5;
task nodestart
    copy skel node:.
    copy *_satsp_euclid node:.
endtask
task main
    copy $tspfile node:.
    node:substitute skel stdin
    node:execute run_satsp_Euclid | grep Final  output
    copy node:output output.$jobname
endtask
task rootfinish
    execute cat output.* | \
        awk '{print $2 " " $3 " " $4 " " $5 " " $6}'  output
    execute post output st70a.tsp  st70a.out
endtask

The nodestart task copies a skeleton skelfile (skel) to the computational node. This file contains formal parameter placeholders, which EnFuzion replaces at runtime. The task also copies to the node, the executable code and a small script, run_satsp_Euclid The run_satsp_Euclid script starts the application, ensuring that the correct binary image is run based on the type of node used. This script also allows the researchers to use a range of computer systems.

The main task copies the required data files to the node before the application is run. The placeholders in the skeleton file are substituted and sent to standard input. The application is run; the output is filtered into the output file. These files are returned to the root machine.

The output was post-processed using the simple filtering program, post, and the UNIX utility, awk. The researchers used the IBM Data Explorer product (DX) to visualize the output. This image shows the effect of varying the parameters on the cost of the solution.

Further Information
This application note describes some basic capabilities of EnFuzion. It uses EnFuzion 6.0 release. You can find out more about using EnFuzion from the user manual or on the Axceleon Web site at www.axceleon.com.