Spin Glass Optimization Problem using Simulated Annealing with Various Cooling Schedules

Abstract

This thesis focuses on searching for solutions to a spin glass optimization problem using the simulated annealing method. This specific spin glass problem involves maximizing the number of +1 entries in a symmetric matrix with +1 and -1 entries by flipping the signs on a row and its corresponding column. We will then describe the basics of the simulated annealing method, which is a probabilistic method for finding solutions to optimization problems where an exhaustive search would be unfeasible. This work introduces several cooling schedules that can be used in simulated annealing and experimentally determines appropriate values for the associated constants and parameters. The various cooling schedules are then used on a randomly-generated starting matrix, and their performances are then compared.