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.
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.
Note that a form of bounded backtrack search can be performed by search/6, but not as a search method as in generic search. Instead, the number of failures during search can be limited by specifying a limit option. For example:
search(Vars, 0, input_order, min, complete,
[limits(gfd_stats{fail:4})] )
limits the number of failures to 4. As it is not a search method, it can be applied to any search method specified in /tt Method.
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, []).
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. However, the search is an atomic process at the ECLiPSe level, and cannot be observed or interacted with, so it is difficult to analyse any unexpected behaviour.
Also, as soon as any user-defined constraints or any other ECLiPSe solvers are involved, or if the built-in search methods are insufficient, 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.
The simplest way to perform search in ECLiPSe is to use generic search’s gfd_search:search/6. The syntax is similar to the built-in search/6, but allows user defined variable selection and value choice methods.
You can also write your own search in ECLiPSe. You can use the generic search’s gfd_search:delete/5 and gfd_search:indomain/2 for variable choice and value selection, but GFD provides primitives that are likely more efficient than the generic versions:
The multi-way choice methods make repeated choices on one variable as gfd_search’s indomain/2.
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).
GFD supports various search support facilities that are not found in ECLiPSe. This section discuss some of these features in more detail.
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:
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 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 (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).