select_var(-X, +Vars, +Handle, +Arg, ?Select)

X

a free variable

Vars

a collection of existing domain variables or terms, or a handle

Handle

free variable, will be bound to handle for remaining collection

Arg

an integer

Select

a predefined selection method.

Description

This predicate picks one domain variable in Vars based on some selection criterion. The selected entry is returned in X. Vars is either a collection of domain variables/terms containing domain variables, or a handle representing domain variables returned in Handle from a previous call to select_var/5.

This predicate provides similar functionality as delete/5 of gfd_search, and is designed to be used in a similar way -- the selection is done on the variables represented in Vars, while Handle is then passed as the next Vars argument for variable selection in the next call to select_var/5, as is done with Rest for delete/5. select_var/5 can thus be used as a replacement for delete/5 in gfd_search:search/6.

The main difference with delete/5 is that Handle is a low-level representation of all the domain variables in Vars, rather than the rest of the domain variables with the selected variable removed as in Rest for delete/5. This allows select_var/5 to be used for both the 'indomain' style labelling (where a selected variable is labelled to different values on backtracking), or the more Gecode-like labelling (where variable selection and a binary value choice is performed for each labelling step). Unlike delete/5, a domain variable that is instantiated will not be selected, and the search is complete when select_var/5 fails because all the domain variables in Vars are instantiated.

When select_var/5 is called with Vars being a collection, the domain variables in the collection are extracted according to Arg in the same way as delete/5, i.e. the Arg'th argument of each element in the collection is the domain variable for that element. In addition to creating the low-level handle representation of the domain variables in Handle, additional initialisation is done for some selection methods that have initialisation parameters (i.e. those involving weighted degree or activity). When select_var/5 is called with Vars being a handle created from a previous call to select_var/5, then Args and any initialisation parameters given with Select are ignored.

Select is one of the following predefined selection methods: input_order, occurrence, anti_occurrence, smallest, largest, smallest_upb, largest_lwb, first_fail, anti_first_fail, most_constrained, most_constrained_per_value, least_constrained_per_value, max_regret, max_regret_lwb, min_regret_lwb, max_regret_upb. max_weighted_degree, min_weighted_degree, max_weighted_degree_per_value, min_weighted_degree_per_value, max_activity, min_activity, max_activity_per_value, min_activity_per_value

These are essentially the same selection methods supported for using Gecode's search engine (search/6), except for random, which is not supported here. For methods that uses activity or weighted degree, Select can include an optional argument in the form of a list, where each list item is a parameter setting. If a parameter is not specified in the list, the default setting for the parameter will be used. These parameters are:

For weighted degree:

• decay(Decay) specify the decay factor (number between 0 and 1, where 1 is no decay). Default is the existing decay factor for weighted degree (normally 1, unless explicitly changed).
• init(Init) set the start values for activity for the search variables according to Init. Init can be:
  • degree(+Factor) set the start value to Factor*degree for the variable. Factor is a non-negative number.
  • vals(Pos,Starts) set the start values to those specified in Starts. Starts is a collection of either the start values (Pos=0), or compound terms containing the value, in the Pos'th argument. The number of start values is the same as the number of variable, and each value is a non-negative number. Starts can be the same collection as Vars, with each item in the collection storing both a variable and its activity start value.
  • none no initialisation (default)

For activity:

• decay(Decay) specify the decay factor (number between 0 and 1, where 1 is no decay). Default is 1.
• init(Init) set the initial values for activity according to Init. Init can be:
  • degree the initial value for each search variable will be the degree (number of propagator) for that variable.
  • vals(Starts) set the initial values to those specified in Starts.Starts is a collection of non-negative numbers, and is the same size as Vars, i.e. each item in Starts represents the initial activity value of the corresponding search variable in Vars. corresponding variable in Vars.
  • none no initialisation (default)

Modes and Determinism

• select_var(-, +, +, +, ?) is semidet

Fail Conditions

Examples

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

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



        % A call with max_activity with parameters
        select_var(V, Vars, Rest, 0, 
                   max_activity([init(degree),
                                 decay(0.9)
                                ])),

See Also