try_value(?Var, ++Method)

Var

a domain variable or an integer

Method

an atom denoting the value choice method

Description

This search predicate makes a choice on the domain of the variable. This choice can be a binary choice, or an indomain style multi-way choice which branches on different values in the domain of the variable.

The binary choice methods create two search alternatives, which reduce the variable domain in complementary ways. The details are determined by the Method.

The first group of binary methods tries to set the variable to a particular value, and in the alternative excludes this value from the domain, logically:

	( Var = Value ; Var #\= Value )

min

try the minimum value in the domain

max

try the maximum value in the domain

median

try the median value in the domain

	( Var #=< Split ; Var #> Split )

split

try first the lower domain half, then the upper

reverse_split

try first the upper domain half, then the lower

indomain_min

Values are tried in increasing order.

indomain_max

Values are tried in decreasing order.

indomain_median

Values are tried starting from the median value of the domain, then alternately the next larger and smaller values in the domain.

indomain_middle

Values are tried starting from the middle of the range (which does not need to be in domain), then alternately the next larger and smaller values in the domain.

indomain_from(+Val)

Values are tried starting from Val (which does not need to be in domain), then alternately the next larger and smaller values in the domain.

As opposed to the value choice predicates indomain/1 and indomain/2, the binary choice methods of try_value/2 does not necessarily instantiate the variable. If used in a tree search, this means that the variable must remain available to the variable selection, as it may be selected repeatedly at different depth of the search tree.

The indomain style methods do instantiate the variable. If used in a tree search, try_value represents a n-ary choice for all the values of a variable. In this case, the maximum depth of the search-tree is the number of problem variables.

This predicate should be more efficient than using generic value choice predicates or explicitly writing code to do the choice. The exclusion of values before a new choice is done by specialised low-level primitives that are more efficient than user-level constraints. This efficiency is particularly important because they make recomputation more efficient. For the binary choice methods, the exclusion of values are performed in every recomputation of the choice; and for the indomain style methods, the old values are excluded from the variable's domain to allow the next value to be chosen. On recomputation, the variable is directly set to the chosen value. This reduces the amount of recomputation, but any reduction in the search space resulting from propagating the exclusion of old values may also be lost.

try_value/2 is best used in combination with select_var/5. Both can be used to parameterise the generic gfd_search:search/6 procedure.

Modes and Determinism

• try_value(?, ++) is nondet
• try_value(+, ++) is det

Examples

    % Used with generic search/6
    gfd_search:search(Xs,0,select_var(first_fail),try_value(min),complete,[]).


    % Simple labelling implemented using select_var/5 and try_value/2
    labelling(Vars, Select, Choice) :-
        (select_var(V, Vars, Rest, 0, Select) ->
            try_value(V, Choice),
            labelling(Rest, Select, Choice)
        ;
            true
        ).