## 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}`

Denys Duchier, Leif Kornstaedt, Martin Homik, Tobias Müller, Christian Schulte and Peter Van Roy
Version 1.4.0 (20080702)