920
K.Z. Gajos et al. / Artificial Intelligence 174 (2010) 910–950unassigned variables are consistent with all size constraints. This allows the algorithm to more quickly detect paths that will not yield a legal solution. Furthermore, it allows the admissible heuristics to make more accurate estimates of the final cost of the complete interface allowing for more efficient branch-and-bound pruning.
In general, full constraint propagation requires time that is quadratic in the number of variables [73]. Note, however, that widget size constraints form a tree structure that mirrors the hierarchy of the functional specification. Exploiting this, Supple performs full propagation of size constraints in linear time. The other types of constraints can form a potentially arbitrary network and Supple uses a one-step forward checking procedure (i.e., propagation of constraints only to the immediate neighbors) for those constraints. The evaluation of the system’s performance (Section 7.4) shows that these optimizations are indeed very effective.
4.3. Variable orderingThe search is directed by the variable ordering scheme encoded in the
selectUnassignedVariable subroutine. Because all variables
are eventually considered, the order in which they are processed does not affect completeness. But, as researchers in constraint satisfaction have demonstrated, the order can have a significant impact on solution time. We have experimented with three variable ordering heuristics
bottom-up first chooses the leaf variables in the interface specification tree (Fig. 1), which leads to construction of the interface starting with the most basic elements, which then get arranged into more and more complex structures.
Top-down chooses the topmost unassigned variable this causes the algorithm to first decide on the general layout and only then populate it with basic widgets. The final heuristic,
minimum remaining values (MRV), has proven highly effective in many constraint satisfaction problems the idea is always to focus on the most constrained variable, that is, the one with the fewest possible values remain- ing.
4.4. Value orderingOrdering of values for each variable is done in a greedy manner, with those with minimum marginal cost being tried first.
While other approaches are common in solving constraint satisfaction problems, we are concerned with finding the best possible interface.
In practice, when the problem is under-constrained, this leads toe cient selection of the best solution while in over-constrained cases, the constraint propagation procedure efficiently eliminates low-cost but large widgets from among the possible values.
Share with your friends: