The configuration problem is a classic problem in constraint satisfaction, with a history that goes back at least as far as R1 and Xcon, the rule-based systems for configuring Vaxen. Today, there are many configurators on the Web--a Google search for “configurators on the Web” yields over 70,000 hits. Even so, the configuration process can still be very complex.

This paper introduces a language, COCONF, that provides for a concept-based encoding of a configuration problem. COCONF, which extends FPC, provides for a “parto-taxonomic” description of the product to be configured, together with a set of constraints that must be satisfied. The parto-taxonomic description encodes into a tree in which the parts, conceived at a conceptual level, fit together to make the assembly. The constraint engine used in the paper makes use of conflict-generated back-jumping, problem decomposition, and two lookahead mechanisms to improve the search process. These are the major intellectual contributions of the paper.

As applications of the system, the author considers three problems, in order of increasing complexity: the configuration of commercial telescopes, bicycles, and computer systems. In each case, the author compares the times to configure using a differing mixture of back-jumping and lookahead strategies. The results show that the lookahead strategies and conflict-generated back-jumping significantly improve performance, solving problems that a naive solver that uses neither lookahead nor lookback is unable to solve within the imposed limit of 300 seconds.

The paper is quite detailed. The formal exposition of COCONF is augmented with detailed examples drawn from the computer system example.