5.12 Distribution

In this section it is shown how Oz supports distribution with constraints. The following procedure creates binary choice-points for variables. The choice is delayed until propagation has reached a fixed point. Assume Dv to be a vector of finite domain integers. The distribution differs in the order of the choice-points and in the constraint with which is distributed. Essentially, it works as follows

• Select an element D of Dv which is not determined.

• Select a value or a domain specification Spec in the current domain of D.

• Create a choice point for X::Spec and X::compl(Spec).

• If not all elements of Dv are determined, go to step 1.

The order of Dv is preserved.

distribute

{FD.distribute +Dist +Xv}

The vector Xv is distributed according to the specification Dist. Dist may be either the atom naive, ff (for first-fail), split or a record with label generic:

• naive: Xv must be a vector of finite domain integers. Considers only non-determined elements of Xv. Chooses the leftmost variable X in Xv. Creates a choice point for X=L and X\=:L, where L is the lower bound of the domain of X.

• ff: Xv must be a vector of finite domain integers. Considers only non-determined elements of Xv. Chooses the leftmost variable X in Xv, whose domain size is minimal. Creates a choice point for X=L and X\=:L, where L is the lower bound of the domain of X.

• split: Xv must be a vector of finite domain integers. Considers only non-determined elements of Xv. Chooses the leftmost variable X in Xv, whose domain size is minimal. Creates a choice point for X=<:M and X>:M, where M is the middle of the domain of X (see FD.reflect.mid).

• generic(order:     +Order  <= size
        filter:    +Filter <= undet
        select:    +Select <= id
        value:     +Value  <= min
        procedure: +Proc   <= proc {$} skip end)

  Considers only those elements in Xv, for which Filter is true. Chooses the leftmost element, which is minimal with respect to Order and selects the corresponding variable D by Select. Creates a choice point for D::Spec and D::compl(Spec), where Spec is selected by Value.

  The values under the respective features must be as follows:

  • Order:

    • Binary boolean function P: Selects the leftmost element in Xv which is minimal with respect to the order relation P.

    • naive: Selects the leftmost variable.

    • size: Selects the leftmost variable, whose domain is minimal.

    • min: Selects the leftmost variable, whose lower bound is minimal.

    • max: Selects the leftmost variable, whose upper bound is maximal.

    • nbSusps: Selects the variable with the largest number of suspensions. If several variables suspend on the maximal number of constraints, the leftmost variable whose domain is minimal is selected.

  • Filter:

    • Unary boolean function P: Considers only the elements X in Xv, for which {P X} yields true.

    • undet: Considers only undetermined variables.

  • Select:

    • Unary function P: Selects the variable to enumerate from the selected element by Order and Filter.

    • id: The variable to enumerate is the selected element.

  • Value:

    • Binary procedure P: Takes a variable as first argument, and binds its second argument to a domain descriptor D to serve as the restriction on said variable to be used in a binary distribution step (D in one branch, compl(D) in the other).

    • min: Selects the lower bound of the domain.

    • max: Selects the upper bound of the domain.

    • mid: Selects the element, which is closest to the middle of the domain (the arithmetical means between the lower and upper bound of the domain). In case of ties, the smaller element is selected.

    • splitMin: Selects the interval from the lower bound to the middle of the domain (see mid).

    • splitMax: Selects the interval from the element following the middle to the upper bound of the domain (see mid).

  • Proc: Is applied when stability is reached. Since this application may cause instability, distribution is continued when stability is reached again.

  Note, that in case Det is det or in case Order is size, lower, upper, or nbSusps, the elements of Xv must be finite domain integers.

  For example, {FD.distribute ff Dv} can be expressed as

  {FD.distribute generic Dv},

  {FD.distribute split Dv} as

  {FD.distribute generic(value: splitMin) Dv},

  and {FD.distribute naive Dv} as

  {FD.distribute generic(order: naive) Dv}

The naive distribution can also be defined as follows using the value feature.

{FD.distribute  
generic(value: fun {$ D}
                  {FD.reflect.min D}
               end) Ds}

choose

{FD.choose +Dist +Xv ?X ?Spec}

Chooses the element X in Xv according to the description Dist. A specification Spec for the element X is returned according to the description Dist. The parameter Dist is defined in the same way as for FD.distribute except for the value selection. If the feature value is used for generic distribution, the field must be constrained to a unary function P which selects a value from the domain of the selected variable (see below for an example). For example,

{FD.choose ff Xs E S}

selects the element E in the list Xs according to the first-fail strategy and binds S to the current lower bound of E.

{FD.choose generic(value:splitMin) Xv E S}

selects the element E in the list Xs according to the first-fail strategy and binds S to the pair 0#M, where M is the result of {FD.reflect.mid E}. For the naive distribution strategy, the following may be used.

{FD.choose generic(value: fun{$ X}
                             {FD.reflect.min X}
                          end)
 Xv E S}