4.11 References and Further Reading

Constraint satisfaction techniques are described by Mackworth [1977a], Dechter [2003], Freuder and Mackworth [2006], and Dechter [2019]. The GAC algorithm was invented by Mackworth [1977b].

Variable elimination 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]. For a more recent overview see Dechter [2019], who calls variable elimination bucket elimination (the buckets contain the constraints to be joined).

Stochastic local search is described by Spall [2003] and Hoos and Stützle [2004]. The any-conflict algorithm is based on Minton et al. [1992]. Simulated annealing was invented by Kirkpatrick et al. [1983]. Xu et al. [2008] describe the use of algorithm portfolios to choose the best solver for each problem instance.

Genetic algorithms were pioneered by Holland [1975]. A huge literature exists on genetic algorithms; for overviews, see Mitchell [1996], Bäck [1996], Goldberg [2002], Lehman et al. [2018], Stanley et al. [2019], and Katoch et al. [2021]

Gradient descent is due to Cauchy [1847].

Python implementations that emphasize readability over efficiency are available at AIPython (aipython.org).