Abstract Simulated annealing has been used extensively to solve combinatorial problems. Although it does not guarantee optimum results, results are often optimum or near optimum. The primary disadvantage is slow speed. It has been suggested  that quenching (rapid cooling) yields results that are far from optimum. We challenge this perception by showing a context in which quenching yields good solutions with good computation speeds. In this paper, we present an algorithm in which quenching is combined with rapid heating. We have successfully applied this algorithm to the multiple-valued logic minimization problem. Our results suggest that this algorithm holds promise for problems where moves exist that leave the cost of the current solution unchanged.