Feature

Learning to predict variable polarity Most solvers treat each instance of a computational problem as independent. Different instances, however, are often related. When solving a new instance, can we reach a solution more quickly by leveraging knowledge gained from past instances? This work [2] explores the possibility of transferring successful low-level solver decisions from solved to unsolved instances, using fine-grained problem structure to identify areas of similarity. Outline of the learning procedure Given a set of related satisfiable problem instances, some previously solved, 1. compute low-level structural features for every variable in solved instances, 2. label each feature vector with the observed satisfying values of its variable, 3. train an efficient binary classifier on these feature vectors, and 4. use the classifier to intelligently initialize your solver for each new instance.