Simulated Annealing and Rapid Quenching

Many combinatorial optimization problems have been successfully attacked using simulated annealing, which was initially developed independently by [10,21]. Simulated annealing approaches resemble local optimum algorithms, except that a random component is introduced which allows occasional ``uphill'' moves (moves which worsen the current solution to the problem according to a cost schedule). As simulated annealing methods have been successfully applied to a wide variety of problems, it seems reasonable to consider adding simulated annealing techniques to Seysen's algorithm in the hope of reducing the number of lcoal minima which cause the algorithm to stop before reaching a global minimum. Modifying Seysen's algorithm to work along the lines of a simulated annealing approach would not be difficult. In the implementation of the algorithm, we simply need to accept row moves which increase the Seysen measure of the lattice basis. The probability of accepting a move which increases S(A) will depend upon the temperature of the reduced lattice, which starts high and decreases according to some cooling schedule and the reduction proceeds. It thus remains to specify the initial temperature of a lattice basis, the probability (as a function of temperature) of accepting a row move which increases S(A), and a cooling schedule which describes how temperature decreases with time/reduction steps. Another technique, based on physical systems, for solving combinatorial optimization problems is the rapid quenching approach. Simulated annealing slowly reduces the temperature of the solution, thus gradually reducing the probability of accepting a move to a higher energy/cost state. Rapid quenching, on the other hand, quickly reduces the temperature in the model, bringing the system to a minimum quickly. The system is then reheated to a temperature lower than the initial temperature, and the process is repeated. Seysen's algorithm itself can be viewed as one iteration of a rapid quenching process. The heated system is the initial lattice basis, and the algorithm itself, by greedily reducing the Seysen measure of the lattice basis, decreases the temperature of the system. We modified our implementation of Seysen's algorithm to simulate multiple rapid quenching iterations. When a lattice basis reached a minimum of the Seysen measure function and no single two-vector row move could decrease S(A), a randomization function was performed on the lattice to ``heat'' it and Seysen's algorithm was subsequently applied to the heated lattice basis. Our randomizing function chose a linear number of pairs of vectors $(\bold{b_i},\bold{b_j}), i \neq j$, and (with equal probability) either added $\bold{b_i}$ to or subtracted $\bold{b_i}$ from $\bold{b_j}$. (This is the same randomizing operation used previously to generate random integer lattices, except that we perform O(n) randomizations here instead of O(n²) as was done before.) Multiple iterations of the heating/Seysen-reducing process did successfully reduce lattice bases more than Seysen-reduction alone, although it is unclear as to how much benefit can be gained from repeated applications of this process.