RAPS: a rule-based language for specifying resource allocation andtime-tabling problems

A general language for specifying resource allocation and time-tabling problems is presented. The language is based on an expert system paradigm that was developed previously by the authors and that enables the solution of resource allocation problems by using experts' knowledge and heuristics. The language enables the specification of a problem in terms of resources, activities, allocation rules, and constraints, and thus provides a convenient knowledge acquisition tool. The language syntax is powerful and allows the specification of rules and constraints that are very difficult to formulate with traditional approaches, and it also supports the specification of various control and backtracking strategies. We constructed a generalized inference engine that runs compiled resource allocation problem specification language (RAPS) programs and provides all necessary control structures. This engine acts as an expert system shell and is called expert system for resource allocation (ESRA). The performance of RAPS combined with ESRA is demonstrated by analyzing its solution of a typical resource allocation problem     

Bayes networks for estimating the number of solutions of constraint networks

The problem of counting the number of solutions to a constraint network (CN) (also called constraint satisfaction problems, CSPs) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree‐structured CNs. For other CNs, it is less optimistic than a spanning‐tree approximation suggested in prior work. Experiments show that the Bayes nets estimation is more accurate on the average, compared to competing methods (the spanning‐tree, as well as a scheme based on a product of all compatible pairs of values). We present empirical evidence that our approximation may also be a useful (value ordering) search heuristic for finding a single solution to a constraint satisfaction problem. This revised version was published online in June 2006 with corrections to the Cover Date.