Previous Up Next

7.4  User defined constraints and solver co-operation

Like IC and FD solvers, GFD has facilities to allow the extension of the solver library so that GFD can co-operate with other solvers in solving a problem, and also to allow the user to define their own constraints at the ECLiPSe level. This is achieved by providing a suspension list with the gfd attribute, which allows for the data-driven programming needed by solver co-operation and constraint propagation, and a set of low-level predicates to process, query and modify the domain of problem variables.

These facilities allow solver co-operation and user-defined constraints propagation at the ECLiPSe level, and not within Gecode directly. So, search then must be done at the ECLiPSe level, i.e. not through Gecode’s search engines. The performance of constraints defined in this way will very likely be less efficient than implementing the constraints directly in Gecode.

7.4.1  The gfd attribute

The GFD attribute is a meta-term which is attached to all GFD problem variables. Many of the fields of the attribute are used for implementing the interface to Gecode, and are of no interest to the user. The only field of interest is the any field, which is for the any suspension list, which is woken on any change in the domain of the variable:

gfd{
   ....
   any:SuspAny,
   ....
}

The any suspension list has the same waking behaviour as the any suspension list of FD, and is sufficient for implementing constraints – the other suspension lists found in IC and FD are specialisations of the any suspension list, in that they provide more precise waking conditions. The reason that only one suspension list is provided by GFD is to minimise the overhead in normal use of the solver.

In addition to waking the attribute’s any suspension list, the constrained suspension list will also be woken when a GFD variable’s domain is changed, and the inst suspension list will be woken if the variable is bound.

The suspension lists allow constraint propagation to be implemented at the ECLiPSe level, which is distinct from the propagation of “native” Gecode constraints, where each propagation phase (and in the case of using the search engine, the whole search) is an atomic step at the ECLiPSe level. This has a similar effect to running all “native” propagations at a higher (more urgent) priority.

As only the any suspension list is provided, some rewriting of existing user-defined constraints for IC and FD may be needed when such code is ported for GFD.

7.4.2  Modifying variable domains

Like IC, GFD provides a set of predicates to modify the domain of GFD variables to support the writing of new constraints. Unlike normal constraints, no Gecode level propagation or waking of other suspended goals (such as scheduled by other ECLiPSe level constraints) occurs with these predicates.

With the exception of impose_bounds/3 none of the goals call wake/0, so the programmer is free to do so at a convenient time.

Some of these predicates are provided for compatibility with IC, as these predicates have the same name and similar semantics to their IC counter-parts (including the waking behaviour for impose_bounds/3). However, due to the difference in the way domains are represented in IC and Gecode, these predicates may be inefficient for use with Gecode, particularly if you need to modify multiple variables and/or multiple domain values. The predicates with names that begin with gfd_vars are specific to GFD and are designed to be more efficient than their IC compatible counter-parts.

The “native” primitives are:

gfd_vars_exclude(+Vars,+Excl)
Exclude the element Excl from the domains of Vars.
gfd_vars_exclude_domain(+Vars, ++Domain)
Exclude the values specified in Domain from the domains of Vars.
gfd_vars_exclude_range(+Vars, +Lo, +Hi)
Exclude the elements Lo..Hi from the domains of Vars.
gfd_vars_impose_bounds(+Vars, +Lo, +Hi)
Update (if required) the bounds of Vars.
gfd_vars_impose_domain(+Vars,++Domain)
Restrict (if required) the domain of Var to the domain specified in Domain.
gfd_vars_impose_max(+Vars,+Bound)
Update (if required) the upper bounds of Vars.
gfd_vars_impose_min(+Vars,+Bound)
Update (if required) the lower bounds of Vars.

The IC-compatible primitives are:

exclude(?Var, +Excl)
Exclude the element Excl from the domain of Var.
exclude_range(?Var, +Lo, +Hi)
Exclude the elements Lo..Hi from the domain of Var.
impose_bounds(?Var,+Lo,+Hi)
Update (if required) the bounds of Var.
impose_domain(?Var,++Domain)
Restrict (if required) the domain of Var to the domain of DomVar.
impose_max(?Var, +Hi)
Update (if required) the upper bound of Var.
impose_min(?Var, +Lo)
Update (if required) the lower bound of Var.

7.4.3  Variable query predicates

These predicates are used to retrieve various properties of a domain variable (and usually work on integers as well).

In most cases, the property is obtained directly from Gecode. Many of these properties are useful for selecting a variable for labelling. Here are some examples:

get_bounds(?Var, -Lo, -Hi)
Retrieves the current bounds of Var.
get_constraints_number(?Var, -Number)
Returns the number of propagators attached to the Gecode variable representing Var.
get_delta(?Var, -Width)
Returns the width of the interval of Var.
get_domain(?Var, -Domain)
Returns a ground representation of the current GFD domain of a variable.
get_domain_size(?Var, -Size)
Returns the number of elements in the GFD domain of Var.
get_max(?Var,-Hi)
Retrieves the current upper bound of Var. Similarly, get_min/2) returns the lower bound.
get_median(?Var,-Median)
Returns the median domain value of the GFD domain variable Var.
get_regret_lwb(?Var, -Regret)
Returns the regret value for the lower bound of Var. Similarly, get_regret_upb/2 for the upper bound.
get_weighted_degree(?Var,-WD)
Returns the weighted degree (wdeg, accumulated failure count) of domain variable Var.
is_in_domain(+Val,?Var,[-Result])
Succeeds iff Val is in the domain of Var. The version with the +Result argument binds Result instead.
is_solver_var(?Term)
Succeeds iff Term is an GFD domain variable.

Previous Up Next