Artificial Intelligence for Engineering Design, Analysis and Manufacturing ~1998!, 12, 383–397. Printed in the USA.
`Copyright © 1998 Cambridge University Press 0890-0604098 $12.50
`
`A classification and constraint-based framework
`for configuration
`
`DANIEL MAILHARRO
`ILOG S.A., 9 rue de Verdun, BP 85, 94253 Gentilly Cedex, France
`
`(Received October 31, 1997; Accepted February 5, 1998!
`
`Abstract
`
`One of the main difficulties with configuration problem solving lies in the representation of the domain knowledge
`because many different aspects, such as taxonomy, topology, constraints, resource balancing, component generation,
`etc., have to be captured in a single model. This model must be expressive, declarative, and structured enough to be
`easy to maintain and to be easily used by many different kind of reasoning algorithms. This paper presents a new
`framework where a configuration problem is considered both as a classification problem and as a constraint satisfaction
`problem ~CSP!. Our approach deeply blends concepts from the CSP and object-oriented paradigms to adopt the strengths
`of both. We expose how we have integrated taxonomic reasoning in the constraint programming schema. We also
`introduce new constrained variables with nonfinite domains to deal with the fact that the set of components is previ-
`ously unknown and is constructed during the search for solution. Our work strongly focuses on the representation and
`the structuring of the domain knowledge, because the most common drawback of previous works is the difficulty to
`maintain the knowledge base that is due to a lack of structure and expressiveness of the knowledge representation
`model. The main contribution of our work is to provide an object-oriented model completely integrated in the CSP
`schema, with inheritance and classification mechanisms, and with specific arc consistency algorithms.
`
`Keywords: Configuration; Knowledge Representation; Constraint Satisfaction Problem; Classification; Taxonomic
`Reasoning; Nonfinite Domains; Resource Balancing
`
`1. INTRODUCTION
`
`1.1. Overview
`A general definition of what we understand by “Configura-
`tion” has been given in Mittal and Frayman, 1989. The con-
`figuration of an artifact is a set of interconnected components
`that are chosen from predefined set of component types, called
`the catalog of component types. Each component type is de-
`fined by a set of attributes that describe its internal charac-
`teristics ~price, geometric dimensions, resource production0
`consumption, etc.!, a set of connection ports that describe
`its relations with other components, and a set of constraints
`on these attributes and ports. The constraints describe com-
`patibility restrictions on component connections ~Type A
`cannot be connected with type B!, limitations on resource
`production0consumption, existential conditions ~compo-
`nent of type A needs component of type B!, etc.
`
`Reprint requests to: Daniel Mailharro, ILOG S.A., 9 rue de Verdun, BP
`85, 94253 Gentilly Cedex, France. E-mail: mailharo@ilog.fr
`
`383
`
`The problem is completely defined by the catalog of com-
`ponent types. During the search for solution, it is impossi-
`ble to define a new type or to modify an existing type by
`adding a constraint, an attribute, or a connection port. This
`is the difference from the design task where such modifica-
`tions are allowed ~Mittal & Frayman, 1989!.
`Given the requirements that the desired product must sat-
`isfy and any specified optimizing criteria, the configuration
`tool must produce
`• the list of the components that are integrated into the
`solution;
`• the type of each of these components;
`• the exact topology of the product, that is, the way the
`components are connected to each other; and
`• the value of the attributes of each component.
`The solution must answer the initial requirements ~which
`can be considered as constraints! and must satisfy all the
`constraints defined on each assembled component. The so-
`lution must be optimal according to the optimizing criteria.
`
`CONFIGIT 1037
`
`1
`
`

`

`384
`
`Configuration has interested industrial and research com-
`munities for 20 yr. Several modeling approaches have been
`proposed, such as expert system, resource-based paradigm,
`terminological logic, object-oriented model, and more re-
`cently constraint satisfaction problem ~CSP!. Each ap-
`proach differs in the knowledge representation model and
`reasoning algorithms employed, but all agree that one of
`the main difficulties with configuration tasks is represent-
`ing the domain knowledge. Configuration needs an expres-
`sive and declarative framework to represent different types
`of knowledge ~Klein, 1996!: taxonomies, structural, arith-
`metic and geometric constraints, part-of and uses relations
`between components, resource production0consumption,
`modularity of components, unknown a priori set of compo-
`nents, etc.
`This knowledge representation aspect of configuration
`tasks is critical in industrial applications for maintenance
`and evolution reasons: catalogs of component types have
`high rates of modification. In the famous example of R10
`XCON ~McDermott, 1982; Barker & O’Connor, 1989!, the
`configurator created at Digital Equipment Corporation to
`build computer systems, the catalog contains 17.000 rules
`and 30.000 component types, and 40% of it is updated each
`year.
`A configuration framework must provide an expressive
`knowledge representation model that is easy to maintain and
`must also provide powerful and efficient algorithms to al-
`low optimization in a highly combinatorial context. An im-
`portant feature is the ability to describe different reasoning
`methods such as constraint propagation, hierarchical refine-
`ment, resource-based balancing, domain-dependent heuris-
`tics, etc.
`
`1.2. Previous work
`A good overview of what has been used to date to represent
`and to solve configuration problems is given in Haselbock,
`1993.
`The rule-based approach is the more commonly used par-
`adigm. However, it seems to be efficient for small problem
`domains only. The main drawback of this approach is the
`maintenance, consistency, and evolutability of the knowl-
`edge base. The problem is that the knowledge is not well
`structured:
`
`• Rules can mix domain knowledge with solving strat-
`egies.
`• Knowledge of a component type is split among several
`rules.
`• Rules are more representative of reasoning steps, that
`is a transition of state, than a declaration of what is a
`component or what must be the configured artifact.
`• A set of rules can be inconsistent.
`The resource-based paradigm ~Heinrich & Jungst, 1991!
`provides an intuitive producer0consumer model but does not
`account well for the topology of the configured artifact. For
`example, a rack produces a resource that is its plugging slots.
`
`D. Mailharro
`
`Each card plugged in this rack consumes one or more slots.
`This kind of knowledge is captured well by resource mod-
`eling, but topological constraints as “cards of type A can
`only be plugged in slots 1 to 8” or “if a card of type A is
`plugged in slot 1, then two cards of type B must be plugged
`in slots 2 and 3” cannot be represented. In real-world con-
`figuration problems, there are topological constraints as well
`as resource balancing constraints. So a framework dedi-
`cated to configuration problems must be able to take into
`account both of the constraint types.
`Another interesting paradigm is the object-oriented ap-
`proach where a configuration problem is considered as a
`Classification problem. Given a generic object and a hier-
`archy of classes that describes the problem domain, the goal
`is to refine the generic object until its correct class in the
`hierarchy is found. This inference process is called taxo-
`nomic reasoning. For example, when configuring a com-
`puter, we know that we need a processor but we do not know
`exactly which concrete type will be chosen in the final com-
`puter. Among the existing applications of this paradigm are
`the Concepts language KL-ONE ~Brachman & Schmolze,
`1985!, the FREEDOM system ~Yokoyama, 1990! which de-
`fines relations between objects as consist-of and contains
`relations, and PLAKON ~Cunis et al., 1989! which defines
`constraints on objects.
`In the configuration domain, representing the compo-
`nents catalog as a class hierarchy is quite natural. The object-
`oriented paradigm strongly improves the maintenance task
`with its specialization and encapsulation concepts. Subtle
`concepts as shared objects and part-of links can easily be
`represented with special classes of object relations. We be-
`lieve this paradigm is adequate to represent the domain
`knowledge required for configuration tasks, and in Section
`3 we explain how we have introduced taxonomic reasoning
`into our constraint-based framework.
`The last paradigm we want to talk about is the CSP one.
`The principle is to “find values for problem variables sub-
`ject to constraints that restrict which combinations of val-
`ues are allowed” ~Sabin & Freuder, 1996!. CSP is an adequate
`framework to represent configuration problems because it
`is “highly declarative, domain independent and simple to
`use”. A configuration problem can be considered as a con-
`straint satisfaction problem where the variables are the type,
`ports, and attributes of each component used in the config-
`ured artifact, and the constraints are the initial requirements
`and the constraints defined in the catalog for each compo-
`nent. Because a configuration task is a generative process
`where the set of the components used in the final solution is
`not known beforehand and is generated during search, the
`basic CSP paradigm cannot be applied directly. The port
`variables’ domain is not complete when creating the vari-
`able because new possible components are generated dur-
`ing search and the constraint network changes each time a
`component is generated.
`Mittal and Falkenheimer ~1990! defines the Dynamic CSP
`~DCSP! as an extension of the basic paradigm that says that
`only a subset of the initial variables may be part of the final
`
`2
`
`

`

`Classification and constraint-based framework
`
`solution. A special kind of constraints called Activity Con-
`straints represent deductions that decide if a variable be-
`longs to the solution or not. This model is not adequate
`because a maximal set of existing variables must be given
`as the specification of the problem. In configuration prob-
`lems, providing the maximal set of possible components may
`be impossible or may produce a huge set that makes the
`search space impracticable.
`Haselbock extends the DCSP model in his ConfCS frame-
`work ~Haselbock, 1993! to handle an unlimited number of
`variables. He uses a generic definition of the domain. Con-
`straints are defined at a meta level between component types.
`Meta variables are used to represent any concrete instance
`of a component type. The constraint is consistent when all
`possible substitutions of the meta variables with existing in-
`stances satisfy the constraint. Because the number of in-
`stances of a type is unlimited, the number of variables of
`the constraint network and the domains of port variables
`are infinite.
`Special constraints called “resource-constraint” are de-
`fined to represent accumulative relations on a part of the
`configuration ~all instances of a given type or all compo-
`nents connected to a given component!. These constraints
`have the unique ability to be defined on a set of variables
`that is not known beforehand and to be able to generate
`new components to ensure consistency. Because configu-
`ration problems are constructive problems ~parts of the ar-
`tifact are generated during search!, this kind of constraints
`on “unknown world” is very useful for expressing knowl-
`edge about what the desired product should be without
`knowing exactly the number or type of the components
`that it will compose. For example, an instrumentation and
`control hardware architecture is composed of a set of pro-
`grammable logic controllers ~PLC!. We do not know how
`many PLCs are needed but we know that the set of PLCs
`has to provide a certain amount of computational power
`and cannot consume more than a certain amount of elec-
`trical power.
`ConfCS takes into account the dynamic and the construc-
`tive aspects of configuration problems well. Its principle lack
`is that its knowledge representation model is not well struc-
`tured; there is no taxonomy of the component types and no
`way to differentiate “part-of” from “uses” relations be-
`tween components. It does not facilitate maintenance be-
`cause knowledge about what is a component is split: activity
`constraints describe the internal structure of a component
`type and compatibility constraints describe the relations be-
`tween its attributes and ports.
`Another important drawback of the Haselbock model is
`for representing 1 2 N relations. When a component a may
`be connected to N components bi, we need to define N ports
`in a: a.p1, a.p2, . . . , a.pN. When the ports are interchange-
`able ~if S is an assignment of the N ports that is a solution,
`any permutation of the values of the ports remains a solu-
`tion!, this model artificially increases the search space by a
`factor factorial N ~N!!. Unfortunately, in real-world appli-
`cations, ports having the same role are often interchangeable.
`
`385
`
`Furthermore, this model is not versatile enough to repre-
`sent variable cardinality. It is impossible to represent a car-
`dinality that is computed by an arithmetic formula, or to
`represent a cardinality that is not limited.
`In our approach, we eliminate these two problems by rep-
`resenting an 1-N relation by one constrained set variable
`with cardinality limited to N instead of N ports. The cardi-
`nality of the set is an integer constrained variable that can
`be computed by a constrained formula. There is no order
`between the values of the set, so the N! permutations of an
`assignment correspond to a single solution: The search space
`is divided by N! compared to the ConfCS approach.
`Sabin and Freuder ~1996! propose another extension of
`the basic CSP paradigm, the composite CSP, which fo-
`cuses on the hierarchical structure of the domain knowl-
`edge. The domain of a constrained variable is a set of entire
`subproblems with their own variables and constraints. When
`instantiating a variable with one of the possible subprob-
`lems, the variables and the constraints of the subproblem
`are added to the constraint network. This approach is able
`to handle a nonlimited set of components, and allows an
`elegant representation of the recursive decomposition of a
`problem into subproblems. However, it is not clear how
`consistency can be maintained on such variables. How can
`the knowledge about the subproblems that belong to the
`domain of a variable be used to deduce which of them are
`inconsistent according to the current state of the variables?
`In the Sabin and Freuder ~1996! example, we are config-
`uring a car. The component engine has two possible types:
`gasoline and diesel. One characteristic of a gasoline en-
`gine is that it consumes 2 fuel units, against 4 fuel units
`for the diesel engine. If our car has to consume less than 3
`fuel units, the diesel type may be removed by an arc con-
`sistency propagation.
`It is not clear also how constraints on an “unknown world”,
`as the resource-constraints of ConfCS, can be expressed.
`
`1.3. Our purpose
`
`Our general aim is to propose a new framework, dedicated
`to the solving of configuration problems, that strongly fo-
`cuses on domain knowledge representation ~because most
`of the complexity lies in its capture! and that allows the de-
`scription of efficient solving algorithms.
`Because we consider a configuration problem both as
`a classification and as a constraint satisfaction problem,
`we have developed a framework that deeply blends con-
`cepts from the object-oriented and CSP paradigms. The goal
`is to provide powerful and expressive tools that can cap-
`ture the different aspects that characterize configuration
`problems:
`
`• The hierarchical structure of the domain knowledge.
`• The critical aspect of maintenance and evolution of the
`components catalog.
`• The generative process ~dynamic constraint network!.
`• The previously unknown set of possible components.
`
`3
`
`

`

`386
`
`• The great variety of constraints ~topological, arithme-
`tic, logical, compatibility, resource balancing, etc.!.
`• The different types of relations between components
`~has-parts, uses!.
`
`Encapsulation and specialization concepts, hierarchical do-
`main CSP ~Mackworth et al., 1985!, and taxonomic reason-
`ing are well suited to structure the domain knowledge in an
`inheritance tree of component types. Maintainability is im-
`proved by the using concepts of the object paradigm, such as
`inheritance or data abstraction, by CSP declarativity and ex-
`pressiveness, and by the clear separation between domain de-
`scription and solving strategies that the CSP paradigm allows.
`Class instantiation is quite natural for representing the gen-
`erative process and the dynamic nature of the constraint net-
`work. CSP is well suited for declaring constraints of various
`types and for describing optimization algorithms and domain-
`dependent heuristics.
`This paper presents the principal features of the knowl-
`edge representation model of our framework and provides a
`simple example extracted from a real-world configuration ap-
`plication on which our approach has been applied. Section 2
`presents the example that will illustrate the further sections.
`Section 3 presents the hierarchical structure of the domain
`knowledge representation and the taxonomic reasoning im-
`plemented as constraint propagations. Section 4 presents ports
`as constraint set variables with nonfinite domains to capture
`the “not known beforehand” set of components. Section 5 de-
`scribes how resource balancing constraints are represented.
`Section 6 details a solution search on the example of Section
`2. Section 7 presents some informal results of a nontrivial ap-
`plication developed with our framework.Aconclusion in Sec-
`tion 8 summarizes the paper and outlines future works.
`
`D. Mailharro
`
`Our framework is based upon the well-known CSP solver
`library Ilog-Solver ~ILOG, 1997!. The code examples pre-
`sented in further sections use the C11 notation.
`
`2. EXAMPLE
`
`The problem is the configuration of an instrumentation and
`control system of an electrical power plant. Such a system
`is composed of a set of programmable logic controllers
`~PLCs!. Each PLC is composed of a set of racks into which
`are plugged processor cards and input0output cards ~I0O
`cards!. A processor provides a certain amount of computa-
`tion power and memory units. An I0O card provides a cer-
`tain number of connections to sensors and actuators. The
`specification of the desired system is given by a set of func-
`tions. Each function specifies the quantities of computation
`power and memory units and the number of analogic, nu-
`meric, and communication connections it needs to be ex-
`ecuted. The task of the configurator is to assign the set of
`functions to a set of processors and I0O cards, and to plug
`these cards into PLC racks. The goal is to minimize the num-
`ber of PLCs needed. There are different types of PLCs, racks,
`processors and I0O cards, and compatibility constraints at
`each connection level. Each hardware component produces
`or consumes resources such as electrical intensity, calorific
`power, plugging slots, computation power, memory, etc. Of
`course all of these resources have to be balanced.
`For the sake of simplicity, we will only focus on an atomic
`part of the problem: the assignment of functions to proces-
`sors ~see Figure 1!. There are three types of functions: FNC,
`the noncritical functions which survey and command sen-
`sors and actuators; FC, the critical ones; and FCOM which
`are in charge of inter-PLC communication. There are three
`
`Fig. 1. Example.
`
`4
`
`

`

`Classification and constraint-based framework
`
`types of processors: XCOM, processors dedicated to com-
`munication tasks; XS100, processors with secured hard-
`ware for critical task execution; and XN400, processors with
`nonsecured hardware. A XS100 processor is composed of
`one secured system component.
`A function is assigned to one processor but one processor
`can contain several functions. Functions consume the com-
`putation power that is produced by processors.
`A Function can only consume the computation power that
`is produced by the processor to which it is assigned:
`
`;p [ Processor, (
`f[functionsp
`
`powerf # powerp.
`
`The global computation power production must be greater
`than or equal to the global consumption:
`
`(
`
`f[Function
`
`powerf # (
`
`p[Processor
`
`powerp
`
`XCOM, XN400, and XS100 produce, respectively, 200, 400,
`and 100 units of computation power. The maximal number
`of functions that can be assigned to an XS100 processor is
`limited to 3.
`The following compatibility rules are:
`
`• XCOM only support FCOM functions.
`• XN400 support FCOM and FNC functions.
`• XS100 support FCOM and FC functions.
`
`There are several instances of each function type. Each
`of these instances specifies its power consumption.
`
`3. CLASSIFICATION AND TAXONOMIC
`REASONING
`
`3.1. Domain knowledge representation
`
`We have adopted the component-oriented model presented
`in Mittal and Frayman ~1989!. A component type is de-
`scribed by a set of attributes and connection ports and by a
`set of constraints. Attributes are implemented with classical
`constrained variables. Ports are constrained set variables
`whose domain corresponds to a nonfinite set of compo-
`nents ~see Section 4 for more details!. Constraints are those
`available in Ilog-Solver ~ILOG, 1997!, plus specific expres-
`sions defined on ports to represent accumulative relations
`on incomplete sets of components. These expressions are
`similar to the “resource-constraints” of ConfCS ~Haselbock,
`1993! ~see Section 5 for more details!.
`Let us give an example of a component type declaration:
`A processor has an integer attribute “power” that represents
`the amount of computation power it provides ~from 0 to
`1000!, a port “functions” that represents the set of functions
`that are assigned to it, and a local resource balancing con-
`straint on computation power:
`
`387
`
`//Objects that represent the component types
`IlcComponentType Processor, Function;
`
`//Declaration of the computation power
`attribute of Processor
`IlcIntAttr power = Processor.addIntAttr-
`(“power”, 0, 1000);
`
`//Declaration of the functions port of Pro-
`cessor
`IlcPort functions = Processor.addPort(Ilc-
`Uses, Function, “functions”);
`
`//Power consumed by the functions connected
`to a processor is
`//less or equal to the power produced by
`this processor
`Processor.add(functions.getSum(“power”) <=
`power);
`
`The component types taxonomy is organized in a
`generalization0specialization hierarchy. Each node of the
`tree describes a type with a set of attributes, ports, and
`constraints that are inherited by subtypes.
`Subtypes can complete their ancestor description with new
`attributes, ports, and constraints. They can also define more
`restrictive bounds for the domain of inherited attributes or
`for the cardinality of inherited ports. For example, XS100
`is a processor that produces 100 units of computation power,
`that can support at most three functions and that is com-
`posed of one secured system component:
`
`IlcConfigurator cfg;
`
`//Declaration of the type XS100 as a sub-
`type of Processor
`IlcComponentType XS100 = cfg.addType (“XS100”,
`“Processor”);
`
`// Bounds restrictions on inherited attributes
`and ports
`XS100.getIntAttr(“power”).setValue(100);
`XS100.getPort(“functions”).setCardMax(3);
`
`//XS100 is composed of exactly one Secured
`system
`XS100.addPort(IlcHasPart, SecuredSystem, 1,
`“secured_system”);
`
`3.2. Instantiation and refinement
`
`The goal of the configuration task is to generate the set of
`components that compose the configured artifact, to put each
`component at the right place in the types hierarchy, and to
`inter-connect these components.
`Component generation is supported by type instantia-
`tion. A component is created with an associated copy of all
`the attributes, the ports, and the constraints defined in the
`instantiated type and with a special constrained variable that
`represents its type. When the instantiated type is not a leaf
`
`5
`
`

`

`388
`
`of the type hierarchy, the component may be refined later
`by a constraint propagation or by an explicit choice point of
`the search procedure. The refinement of a component cor-
`responds to a more accurate knowledge of what can or what
`must be the final implementation of the component. Thus,
`when a component is refined, it becomes an instance of one
`of the descendant types of its current type, and so all the
`attributes, ports, and constraints defined for its new type
`~except those inherited from its current type! are added to
`the current constraint network.
`In our previous example, if we have the instance aPro-
`cessor that is refined from processor to XS100, restrictions
`on its “power” and “functions” variables are per-
`formed and a “secured_system” port is added to it, as
`illustrated in Figure 2.
`The refinement procedure is powerful because it allows
`reasoning on a partial description of a component. Infer-
`ences can be made on a component without knowing ex-
`actly what its concrete implementation in the final artifact
`will be. Propagations can be performed on the possible types
`of a component to decide which types remain possible or
`become required after an event occurs on any constrained
`variable domain. For example, we know that our config-
`ured artifact needs a processor but we do not know which
`kind of processor. So, we can create an instance of the ge-
`neric type processor, and begin to work on it with the par-
`tial knowledge we have of it, for example, the computation
`power it provides must be greater than or equal to the sum
`of the computation power consumed by the functions that
`are assigned to it. Then, when assigning functions to it, de-
`ductions on its possible types are activated. For example, if
`the quantity of consumed power becomes greater than 100
`units, XS100 becomes inconsistent. Or if an FC function is
`assigned to it, compatibility constraints propagate that only
`XS100 is consistent and the processor is then refined to
`XS100.
`This mechanism gives great flexibility for writing search
`algorithms because choosing the type of a component can
`be separated from the component generation. There are three
`
`D. Mailharro
`
`important operations on a component: its creation, its clas-
`sification, and its connection with other components. Cre-
`ation is always the first operation, but there is no mandatory
`order for the two others. A component can be connected be-
`fore being classified or can be classified before being con-
`nected. It is also possible to interlace the two operations:
`we can decide to connect some of its ports, then to refine it
`until a certain level, then to connect some others of its ports,
`then to refine it again, etc. It is also possible to delay one
`operation by making choice points on other parts of the con-
`figured artifact, hoping that these choices will make inter-
`esting propagations on our component.
`It is interesting to note that the refinement procedure is
`perfectly integrated in the CSP schema because it has a
`monotonic behavior. The set of the possible refinements for
`a given type is a subset of the possible refinements of its
`ancestor types. So refining a component consists in reduc-
`ing the set of its possible classifications, that is, refinement
`can only reduce the domain of the constrained type variable
`of a component.
`
`3.3. Type variables
`
`Each component has a constrained variable that represents
`its type. We call it the type variable of the component. This
`variable has a hierarchical domain as defined in Mack-
`worth et al. ~1985!. The variable is bound only when it is
`impossible to refine the component more. In other words,
`the variable can only be instantiated with leaf types of the
`hierarchy. This corresponds to the fact that the configured
`artifact must finally be built with concrete component types
`available in a constructor catalog. In our example, it is not
`sufficient to say that the system contains a processor; the
`configurator must decide exactly if it is a XS100, a XN400,
`or an XCOM.
`Inferences made on the type variable are as follows:
`
`1. When a type is inconsistent, then so are all its descen-
`dents ~see Figure 3b!.
`
`Fig. 2. Refinement procedure: @0..1000# denotes a constrained integer variable whose value is between 0 and 1000. @0..1# denotes a constrained integer
`variable whose maximal value is the infinity. ~ ! @0..5# denotes a constrained set variable whose cardinality is between 0 and 5.
`
`6
`
`

`

`Classification and constraint-based framework
`
`389
`
`Fig. 3. Inferences on type variables.
`
`2. When a type is inconsistent and when it was the sole
`descendent of its father, then its father is also incon-
`sistent ~see Figure 3c!.
`3. When the component is refined to a given type, then
`only the ancestors and the descendents of that type re-
`main consistent ~see Figure 3d!.
`4. When a type becomes inconsistent and when only one
`possible descendent for the current type of the com-
`ponent remains, then the component is refined to that
`descendent type ~see Figure 3e!.
`
`Because of the subsumption semantic that exist between
`a leaf type and its ancestors, we can easily imagine that the
`value of a type variable is an implicit set of component types
`that correspond to the oriented simple path from a root type
`to a leaf type along the subsumes links. For example, if a
`component is refined to the type XS100, the value of its
`type variable is $Processor, XS100% since an XS100 in-
`stance is also an instance of Processor. We can deduce the
`two following properties:
`
`• A possible path contains only possible component types.
`• A possible type belongs to at least one possible path.
`
`The soundness of previous inferences can be easily showed
`with this properties. From the first property, we can say that
`if a type becomes impossible, all the paths that include it
`becomes impossible values for the type variable ~inference
`1!. From the second property, we can deduce that when a
`path becomes impossible, each of its nodes that no more
`belongs to a possible path, becomes impossible ~inference
`2!. When a component is refined to a component type, only
`
`the path that includes this type remain possible ~inference
`3!. If a type T belongs to all the possible paths, the compo-
`nent can be refined to this ~inference 4!.
`
`a. The initial possible paths are:
`
`~ $A-B-F% $A-B-G% $A-C-H% $A-D-I% $A-E-J% $A-E-K% $A-E-L% !
`
`A belongs to all the possible paths, so the component
`is refined to A.
`
`b. E becomes impossible. All the paths that contain E are
`removed:
`
`~ $A-B-F% $A-B-G% $A-C-H% $A-D-I% !
`
`J, K, L do not belong to a possible path: they become
`impossible types.
`
`c. H becomes impossible. All the paths that contain H
`are removed:
`
`~ $A-B-F% $A-B-G% $A-D-I% !
`
`C does not belong to a possible path: it becomes an
`impossible type for the component.
`
`d. Only paths containing B remain possible:
`
`~ $A-B-F% $A-B-G% !
`
`e. G becomes impossible. All the paths that contain G
`are removed:
`
`~ $A-B-F% !
`
`7
`
`

`

`390
`
`The component is refined to F because F belongs to all
`the possible paths.
`
`4. TOPOLOGY: NONFINITE DOMAIN FOR
`PORT VARIABLES
`
`4.1. Motivation
`
`The topology of the configured artifact, that is the descrip-
`tion of the interconnections of its components, is com-
`pletely represented by port constrained variables assignment.
`In our framework, a port is typed, that is, only components
`of a given type can be connected to it. Connections between
`components are always constrained by such type restric-
`tions; only cards can be plugged into racks. Because a type
`defines a subset of the entire existing components set, typ-
`ing a port reduces its domain size, and thus, reduces the
`size of the search space.
`In configuration problems the set of the components is
`not known beforehand, and sometimes even the size of the
`set cannot be estimated. The problem with classical con-
`strained variables is that the set of the possible values must
`be known before creating the variable, so it is impossible to
`define the domain of port variables.
`However, we wanted to have port variables that would
`be able to represent partial connections and to post con-
`straints that could generate new components to insure con-
`sistency. Even if the components do not exist yet, we wanted
`to express constraints such as “The sum of the size of the
`cards that are plugged into a rack cannot exceed the capac-
`ity of the rack”. We wanted to make generative inferences
`that create a new component each time there is no existing
`component that can satisfy the constraint. For example, we
`know that a processor produces at most 1000 units of com-
`pu