4.12 References and Further Reading

Constraint satisfaction techniques are described in Dechter (2003) and Freuder and Mackworth (2006). The GAC algorithm was invented by Mackworth (1977). The DPLL algorithm was invented by Davis et al. (1962).

VE for propositional satisfiability was proposed by Davis and Putnam (1960). VE for optimization has been called non-serial dynamic programming and was invented by Bertelè and Brioschi (1972).

Stochastic local search is described by Spall (2003) and Hoos and Stützle (2004). The any-conflict heuristic is based on the min-conflict heuristic of Minton et al. (1992). Simulated annealing was invented by Kirkpatrick et al. (1983). Genetic algorithms were pioneered by Holland (1975). A huge literature exists on genetic algorithms; for overviews see Goldberg (1989), Koza (1992), Mitchell (1996), Bäck (1996), Whitley (2001), and Goldberg (2002).