PPT Slide
DP provides very challenging benchmark for comparisons with other systematic (complete) procedures.
Not just on random formulas!
Many other methods have been tried, e.g.,
1) Backtracking with sophisticated heuristics
(Purdom 1984; Zabih and McAllester 1988; Andre and Dubois 1993; Bhom 1992; Crawford and Auton 1993; Freeman 1993, etc.)
2) Translations to integer programming
(Jeroslow 1986; Hooker 1988; Karmarkar et al. 1992; Gu 1993)