DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems (many good papers).
SAT: references on satisfiability.
O. Kullmann papers, links, and software for the SAT problem.
V. Kumar.
Algorithms for Constraint-Satisfaction Problems: A Survey.
AI Magazine 13(1):32-44, 1992.
For more general references on constraint satisfaction, see
The Constraints Archive.
E. Dantsin, A. Goerdt, E. A. Hirsch, and U. Schöning. Deterministic algorithms for k-SAT based on covering codes and local search. Proc. 27th Int. Coll. Automata, Languages and Programming, 2000.
U. Schöning. A probabliistic algorithm for $k$-SAT and constraint satisfaction problems. Proc. 40th Symp. Foundations of Computer Science, IEEE, October 1999, pp. 410--414. (Hardcopy is in graduate filing cabinet, CS building 4th floor elevator lobby near coffee room.)
D. Eppstein and R. Beigel. 3-coloring in time O(1.3289^n). (See this extended abstract for a gentler introduction.)
D. Eppstein. Small maximal independent sets and faster exact graph coloring.
Systematic Generation of Very Hard Cases for Graph 3-Colorability, R. Vlasie.
Concorde: a code for solving traveling salesman problems.
D. M. Warme, P. Winter, and M. Zachariasen. Exact solutions to large-scale plane Steiner tree problems.
Practical application of large-scale exponential search in optimizing fast software encryption code