  Global changes of states are of crucial importance in optimization
algorithms. We review some heuristic algorithms in which global updates are
realized by a sort of real-space renormalization group transformation. Emphasis
is on the relationship between the structure of low-energy excitations and
``block-spins'' appearing in the algorithms. We also discuss the implication of
existence of a finite-temperature phase transition on the computational
complexity of the ground-state problem.
