The Splitting Method for Decision Making

Abstract

We show how a simple modification of the splitting method based on Gibbs sampler can be efficiently used for decision making in the sense that one can efficiently decide whether or not a given set of integer program constraints has at least one feasible solution. We also show how to incorporate the classic capture-recapture method into the splitting algorithm in order to obtain a low variance estimator for the counting quantity representing, say the number of feasible solutions on the set of the constraints of an integer program. We finally present numerical with with both, the decision making and the capture-recapture estimators and show their superiority as compared to the conventional one, while solving quite general decision making and counting ones, like the satisfiability problems.

Keywords:

• Combinatorial optimization
• Counting
• Cross-entropy
• Decision making
• Gibbs sampler
• Rare-event
• Splitting

Mathematics Subject Classification:

• 65C05
• 60C05
• 68W20
• 90C59

Acknowledgment

This research was supported by the BSF (Binational Science Foundation, grant No. 2008482).