Constraint and Variable Ordering Heuristics for Compiling Configuration Problems

Nina Narodytska, Toby Walsh

To facilitate interactive design, the solutions to configuration problems can be compiled into a decision diagram. We develop three heuristics for reducing the time and space required to do this. These heuristics are based on the distinctive clustered and hierarchical structure of the constraint graphs of configuration problems. The first heuristic attempts to limit the growth in the size of the decision diagram by providing an order in which constraints are added to the decision diagram. The second heuristic provides an initial order for the variables within the decision diagram. Finally, the third heuristic groups variables together so that they can be reordered by a dynamic variable reordering procedure used during the construction of the decision diagram. These heuristics provide one to two orders magnitude improvement in the time to compile a wide range of configuration.