AAAI Publications, Workshops at the Twenty-Seventh AAAI Conference on Artificial Intelligence

Font Size: 
Throwing Darts: Random Sampling Helps Tree Search when the Number of Short Certificates is Moderate
John Paul Dickerson, Tuomas Sandholm

Last modified: 2013-06-29


One typically proves infeasibility in satisfiability/constraint satisfaction (or optimality in integer programming) by constructing a tree certificate. However, deciding how to branch in the search tree is hard, and impacts search time drastically. We explore the power of a simple paradigm, that of throwing random darts into the assignment space and then using information gathered by that dart to guide what to do next. This method seems to work well when the number of short certificates of infeasibility is moderate, suggesting that the overhead of throwing darts is more than paid for by the information gained by these darts.


search; sampling; proving optimality; proving infeasibility

Full Text: PDF