Determining the Most Promising Selective Backbone Size for Partial Knowledge Compilation

Knowledge compilation allows for quick retrieval of a wide variety of information about an instance of a constraint satisfaction problem or Boolean formula. Unfortunately, the compiled representation can be so large that it cannot be used in practical settings, especially when there are restrictions on the amount of available memory. It has been recently observed that assigning some carefully chosen variables can significantly reduce the size of the representation, with only a small loss of data about the instance. However determining how many, and which, variables should be assigned to create a compact compiled instance requires making a number of expensive computations, including completely compiling the full initial instance, which might not be achievable for large instances. Our work in this paper involves removing large compilations from the process of constructing selective backbones. First we look at how statistical properties of literals can be used as fast heuristics to pick which variable to assign next. Then we show how the behaviour of selective backbones for small instances can help determine the size at which selective backbones for large instances are expected to offer the best compromise between the quantity of knowledge lost and the amount of space saved. We also extend previous work to take into account weighted preferences on models. This is beneficial since various probabilistic models can be expressed in such terms.