  This paper gives a straightforward implementation of simulated annealing for
solving maximum cut problems and compares its performance to that of some
existing heuristic solvers. The formulation used is classical, dating to a 1989
paper of Johnson, Aragon, McGeoch, and Schevon. This implementation uses no
structure peculiar to the maximum cut problem, but its low per-iteration cost
allows it to find better solutions than were previously known for 40 of the 89
standard maximum cut instances tested within a few minutes of computation.
