Automating the Construction of Patchers That Satisfy Global Constraints

Abstract

Generate-and-test algorithms to solve constraint satisfaction problems are often inefficient, but can be constructed fairly easily by knowledge compilation techniques that convert declarative problem knowledge and domain knowledge into a procedural format [Liew and Tong, 1987]. Current research is focusing on methods to improve the efficiency of generate-and-test algorithms by completely incorporating local constraints into generators of parts of composite solutions [Braudaway, 1988]. More global constraints on multiple parts cannot necessarily be incorporated into the part generators. Their satisfaction must be ensured in a different way. We describe an (unimplemented) method for transforming a generate-and-test algorithm into a generate-test-and-patch algorithm that efficiently hillclimbs toward a solution satisfying a particular global constraint. Our method is based on constructing an evaluation function from the global constraint, that reflects the "degree" to which the constraint has been satisfied. Some of the steps in this method rely on categorizing the global constraint into a generic class. In this paper, the constraint classes on which we focus are quota-meeting and covering constraints. We illustrate the general approach by applying it to a simple generate-and-test algorithm for house floorplanning. We provide empirical results that corroborate our claim that the efficiency of the algorithm has been significantly improved.