Randomized local search method are receiving a lot
 of attention. These methods are seldom truly random,
 as some level of search guidance usually is present.
 In this talk we look at the tradeoff issues between
 randomization and the quality of search guidance.

 We have chosen Satisfiability problems (SAT) because
 they are capable of representing many important
 real-world problems, like planning, scheduling, and
 robotic movement.  Efficient encodings exist for many
 of these applications and thus having good solvers for
 these problems can thus be very useful.

 Our search guidance is based on the use of Surrogate
 Constraints. More specifically we look at how adaptive
 memory and surrogate constraint processes can be used
 as search guidance for both constructive and local
 search heuristics for satisfiability problems, and how
 most well-known heuristics for SAT can be seen as
 special cases. We also discuss how adaptive memory
 learning processes can reduce the customary reliance
 on randomization for diversification so often seen in
 the literature. The important issue here is the tradeoff
 between the cost of maintaining extra memory search
 guidance structures and the potential benefit they have
 on the search in term of a better search focus.

 We illustrate the different tradeoffs on a portfolio of
 satisfiability problems from SATLIB.