Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.4. PROPERTIES OF A DESIGN

We now define two important properties of a design, each expressed in terms of properties of constraints and parts, i.e., consistency and decomposability, that are derived from the constraint-satisfaction problem (CSP) literature (van Beek, 1992; Mackworth, 1977). Such problems are described by a set of variables, a set of domain values for each variable, and a set of constraints, and their solutions are an assignment of values to variables that satisfies the constraints. Clearly, consistency and decomposability are implicit in any design system that uses propagation to rule out assignments to unassigned variables (consistency) in order to find a solution to the problem (decomposability).

A constraint is consistent if for each attribute in the constraint's argument and every assignment to that attribute, there exist values for all the other attributes that satisfy the constraints (Mackworth, 1977). If a constraint is consistent, then each of the constraint's arguments is consistent with respect to the constraint, and each argument domain value is a consistent value. The consistency propagation function is defined such that it generates a consistent set of values for some constraint argument with respect to the constraint.

Consistency also applies to catalogs and design spaces. A catalog is a consistent catalog if each catalog attribute is consistent with respect to each constraint in which it appears in the constraint's arguments. If a catalog is a consistent catalog, then each part in the catalog is a consistent part. A design space is a consistent design space if each constraint is consistent.

To illustrate the consistency property, we return to the example introduced earlier. Consider the total-weight constraint. Solving for each term yields the propagation functions:

  • machine-unit.weight [lte] 2760 - motor.weight
  • motor.weight [lte] 2760 -- machine-unit.weight

These propagation functions restrict the allowed assignments to machine-unit weight and motor weight, respectively, given the assignment to the other attribute. The first function is interpreted as follows for the consistency property: for each possible machine-unit weight, there exists a motor such that the constraint is satisfied. If no such motor exists for a given machine-unit, then that machine-unit is not consistent and should be removed.

For example, the parts model38 and model58 can be eliminated from consideration without losing any solutions, since if either model38 or model58 is selected, there is no motor light enough to satisfy the total-weight constraint. Removing inconsistent parts reduces the search space and eliminates the dead-ends that would result if these parts were selected. Table 3 shows the catalogs with all inconsistent parts removed.

Decomposability is a stronger property than consistency. Decomposability means that all designs in the design space satisfy all the constraints (van Beek, 1992). In other words, all designs are guaranteed to satisfy all constraints. If a constraint is decomposable, then each of the constraint's arguments is decomposable with respect to the constraint.


TABLE 3
The Catalog of Table 2 Modified to Show Only Consistent Parts
 
(a) machine-unit catalog
 
part_name min_hp max_hp weight
 
model18 10 15 1100
model28 15 20 1700
 
(b) motor catalog
 
part_name hp weight
10HP 10 374
15HP 15 473
20HP 20 534

Decomposability also applies to catalogs and design spaces. A catalog is a decomposable catalog if each catalog attribute is decomposable with respect to each constraint in which it appears in the constraint's arguments. If a catalog is a decomposable catalog, then each part in the catalog is a decomposable part. A design space is a decomposable design space if each constraint is decomposable.

To illustrate the decomposability property, consider the constraints between the machine-unit minimum and maximum horsepower and the motor horsepower shown below:

  • machine-unit.min_hp [lte] motor.hp
  • motor.hp [lte] machine-unit.max_hp

The first function is interpreted as follows for the decomposability property: for each possible pair of machine-units and motors, the constraint is satisfied. By examination, the constraint is not decomposable, since there exists an assignment that violates the constraint, namely, machine-unit.min_hp = 15 and motor.hp = 10. Thus, to satisfy this constraint, an effective heuristic for monotonic constraints such as these removes the machine-unit with value min_hp = 15 and the motor with value hp = 10. Removing infeasible designs using this heuristic moves the constraint toward decomposability. This heuristic does not guarantee that only infeasible designs are removed, however. For example, there may be a feasible design that contains a 10-horsepower motor. If necessary in a case such as this, backtracking is initiated to re-introduce removed parts.

Finally, the time it takes to confirm consistency and to explore decomposability are central to practical configuration-design systems. While consistency is achieved in linear time, decomposability is achieved in worst-case exponential time. There is a class of CSPs where the constraints are monotonic and the variable domain values are single-valued, in which case decomposability can be achieved in linear time (Deville and Van Hentenryck, 1991). This is a very fortunate result since a large number of the constraints in configuration-design problems are monotonic.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.