Previous Up Next

7.3  Search Support

GFD allows search to be performed in two ways: completely encapsulated in the external Gecode solver, or in ECLiPSe, supported by GFD’s variable selection and value choice predicates.

Additionally, GFD support various search facilities of Gecode that is not directly supported by IC. These are described in section 7.3.3.

7.3.1  Performing search completely inside Gecode

Search can be performed in Gecode using one of its search engines. In this case, the search to produce a solution appears as an atomic step at the ECLiPSe level, and backtracking into the search will produce the next solution (or fail if there are none), again as an atomic step.

This direct interface to Gecode’s search engines is provided by gfd:search/6, and uses a syntax similar to that of the generic search/6 predicates (in lib(gfd_search) (see below), lib(ic) and lib(fd_search)).

As the search is performed in Gecode, it should be more efficient than doing the search in ECLiPSe, where the system has to repeatedly switch between Gecode and ECLiPSe when doing the search. As the search is a single atomic step from the ECLiPSe level, it is not suitable if your code needs to interact with the search, e.g. if you are using constraints defined at the ECLiPSe level, and/or if you are using other solvers during the search.

On the other hand, GFD’s search/6 is less flexible than the generic search – you can only use the predefined variable selection and value choice methods, i.e. you cannot provide user-defined predicates for the Select and Choice arguments.

The search engine to use is specified by the Method argument in search/6. One method provided by Gecode is bb_min – finding a minimal solution using branch-and-bound, which is not provided by the generic search.

Instead, branch-and-bound in ECLiPSe is provided by lib(branch_and_bound), which can be used with generic search’s search/6 to provide a similar functionality as the bb_min method of GFD’s search/6. The ECLiPSe branch-and-bound is more flexible, but is likely to be slower. Note that lib(branch_and_bound) can be used in combination with GFD’s search/6, but this is probably not useful unless you are doing some search in your own code in addition to that done by search/6, or if you want to see the non-optimal solutions generated by the search.

There are some differences in how search is performed by Gecode and generic search; the most significant is that all the built-in choice-operators of the generic search library make repeated choices on one variable until it becomes ground, before proceeding and selecting the next variable. Gecode’s built-in strategies on the other hand always interleave value choices with variable selection.

Other differences from generic search are:

Here is the N-Queens example using GFD’s search/6:

:- lib(gfd).

queens_list(N, Board) :-
    length(Board, N),
    Board :: 1..N,
    (fromto(Board, [Q1|Cols], Cols, []) do
        ( foreach(Q2, Cols), param(Q1), count(Dist,1,_) do
            Q2 #\= Q1,
            Q2 - Q1 #\= Dist,
            Q1 - Q2 #\= Dist
        )
    ),
    search(Board, 0, input_order, indomain_min, complete, []).

7.3.2  Search in ECLiPSe using GFD primitives

The built-in Gecode search is appropriate when the problem consists exclusively of GFD-variables and GFD-library-constraints, and when the built-in search methods and search heuristics are sufficient to solve the problem.

As soon as any user-defined constraints or any other ECLiPSe solvers are involved, then the top-level search control should be written in ECLiPSe, in order to allow non-gfd propagators to execute between the labelling steps. Also the implementation of problem-specific search heuristics will usually make it necessary to lift the top-level search control to the ECLiPSe level. To make this possible, GFD provides primitives to support variable selection and value choice heuristics.

gfd:select_var(-X, +Collection, -Rest, ++Arg, ++Select)
Select a domain variable from Collection according to one of Gecode’s pre-defined selection criteria. These include criteria not available in other ECLiPSe solvers, like accumulated failure count.
gfd_search:delete(-X, +Collection, -Rest, ++Arg, ++Select)
Select (and remove) a domain variable from Collection. This is the generic implementation, (compatible with IC and FD solvers), providing a different choice of selection options, but likely to be less efficient than select_var/5.
gfd:try_value(?Var, ++Method)
This value choice predicate supports both Gecode-style binary choice and generic search’s multi-way choice on the domain of a variable, according to Method. The binary-choice methods create two search alternatives, which reduce the variable domain in complementary ways. Because the variable is not necessarily instantiated, this must be combined with a variable selection method that does not delete the selected variable, such as select_var/5.

The multi-way choice methods make repeated choices on one variable as gfd_search’s indomain/2.

gfd:indomain(?Var)
Instantiate Var to elements in its domain, using a default method.
gfd_search:indomain(?Var, ++Method)
A flexible way to nondeterministically assign values to finite domain variables according to Method. On success, Var is always instantiated. This is the generic implementation (compatible with IC and FD solvers), providing a different choice of methods, and likely to be less efficient than try_value/5.

A simple search using GFD’s primitives can be defined in the following way:

labeling(Vars, Select, Choice) :-
        ( select_var(V, Vars, Rest, 0, Select) ->
            try_value(V, Choice),
            labeling(Rest, Select, Choice)
        ;
            true
        ).

For binary choice methods of try_value/2, the search will mimic Gecode’s built-in search (where a variable selection step is usually interleaved with a binary choice on the variable domain).

For multi-way choice methods of try_value/2, (possibly several) value choices on a variable are made until the variable is ground, before proceeding to select the next variable: On backtracking to the try_value/2, alternative values for the variable will be tried. This mimics the behaviour of gfd_search’s indomain/2, but try_value/2 is likely to be more efficient as it is specifically tailored for GFD.

The same effect can be achieved by using select_var/5 and try_value/2 together with the generic gfd_search:search/6 predicate:

gfd_search:search(Vars, 0,
        select_var(Select), try_value(Choice), complete, [])

Several selection methods predicates that are designed to be used with generic search, are provided: max_regret_lwb/2, max_regret_upb/2, max_weighted_degree/2, max_weighted_degree_per_value/2, most_constrained_per_value/2. These allow selection methods supported in GFD but not in generic search to be used with gfd_search:search/6.

For even more complex user-defined heuristics, various properties associated with a variable and its domain can be obtained using predicates described in section 7.4.3. Note that these include properties that are not available in ECLiPSe’s solvers, such as weighted degree (a.k.a. accumulated failure count).

7.3.3  GFD specific search support

GFD supports various search support facilities that are not found in ECLiPSe. This section discuss some of these features in more detail.

Dynamic measure of propagation

Gecode supports two ways of dynamically measuring constraint propagation for variables. These measures can be used in variable selection heuristics that ’learn’ from the actual propagations of the program. Such heuristics may perform better, and is particularly suited to Gecode’s interleaving of variable selection and value choice. The two measures are:

weighted degree
Known as Accumulated Failure Count in Gecode. Count of the number of failures in constraints associated with the variable. Count is updated after each propagation failure.
activity
Count of the number of domain reduction on the variable during propagation. Count is updated after each propagation.

As the search normally starts immediately after modelling, there would be very little constraint propagation, so both measures will not have much information to be used for variable selection. One way to work around this is to assign initial values to the counts, to give reasonable start values. This is the reason that, by default, the initial value for weighted degree of a variable is set to its degree.

For gfd:search/6, an alternative to setting the initial values is to use the tiebreak/1 option to use a tie-breaking selection method. Another alternative is to use restart-based search, with the initial search acting as a ’probe’ to obtain good values for the measures for the ’real’ search.

Gecode also supports a decay factor for both measures, where the count values can be reduced by the decay factor if their count is not incremented when the measure is updated: The idea is to favour those variables that are involved in the propagation most recently.

GFD supports setting of both the initial values and the decay factor for variable selection methods that uses weighted degree and activity via parameters in gfd:search/6 and select_var/5.

Weighted degree is computed for all variables, and can be obtained with get_weighted_degree/2. It can be re-initialised using init_weighted_degree/1. The decay factor can be obtained by get_weighted_degree_decay/1 and set with set_weighted_degree_decay/1.

Due to the way activity is implemented by Gecode, the use of activity in GFD is limited to the variable selection methods for search/6 and select_var/5.

Note also activity is computed for recomputation as well as normal computation, so changing the amount of recomputation (by changing the cloning distance) can change the activity counts for the same problem, thus affecting the search if an activity based selection method is used.

Restart-based search methods

Restart is a technique supported by Gecode, where the current search is abandoned and restarted from the root, allowing the restarted search to make different branching choices, and send the search to a different part of the search space. This is useful if the old search was not fruitful in getting a solution, so exploring a different part of the search space may prove better than continuing the old search.

The restarted search will only be different from the old search if different branching choices can be made, e.g. if at least some of these choices are random, or if some of the choices have a learning component, e.g. variable selection methods that uses activity or weighted degree.

The branching choices can also be different if the restarted search is more constrained. Gecode supports no-goods learning, an automatic technique for remembering failures in the old search, and posting ’no-good’ constraints for the new search that prevent the search from repeating these failures.

Restart-based search is not complete, and is mostly useful for finding a single solution, rather than many solutions.

GFD provides two search methods for gfd:search/6 that are restart-based: restart and restart_min. Both methods will only find one solution.

Lightweight Dynamic Symmetry Breaking

Lightweight Dynamic Symmetry Breaking (LDSB) is a symmetry breaking technique implemented for Gecode’s search engines, and for IC in ECLiPSe with lib(ldsb). Currently, GFD supports LDSB for gfd:search/6 only, as lib(ldsb) is written for IC only.

LDSB is supported in gfd:search/6 by the ldsb_sym/1 option, where the symmetries for the problem are specified, and can be used for all value choice method. This is unlike lib(ldsb), where LDSB is supported by separate predicates, including predicates to perform value choice, rather than being integrated into the generic search

The syntax for the symmetry specifications follow those used in lib(ldsb). In particular, the definition of rows and columns for a 2-D matrix is the one used in ECLiPSeand in lib(ldsb), but not in Gecode (where the definitions are reversed). That is, the matrix are organised as collection of rows.

While LDSB is not currently available for GFD at the ECLiPSelevel, Symmetry breaking is available via SBDS (Symmetry Breaking During Search) in lib(gfd_sbds).


Previous Up Next