Optimizing simulated annealing

The method of simulated annealing was used to get a heuristic solution for the minimum length word equivalent to a given word in the braid groups (a known NP-complete problem). The simulated annealing paradigm with a simple cooling schedule leaves five parameters up to the user to choose that were chosen empirically based on performance experiments as is the usual practise. After this, a downhill simplex method was developed to further optimize these critical parameters and a quality improvement of up to 26.1% was observed. This additional improvement made the algorithm competitive, on average, with custom designed heuristics for this problem. The conclusions going beyond the present combinatorial problem are: (1) Fine-tuning of cooling schedule parameters is critical for the solution quality in simulated annealing, (2) downhill simplex methods (as opposed to Newton's method, for example) are well-suited for this task and (3) significant quality improvement is possible even for a simple cooling schedule.