[ library(gfd) | Reference Manual | Alphabetic Index ]

search(+L, ++Arg, ++Select, +Choice, ++Method, +Option)

Interface to gecode search-engines to perform search in gecode.
L
is a collection (a la collection_to_list/2) of (domain) variables (Arg = 0) or a collection of terms (Arg > 0)
Arg
is an integer, which is 0 if L is a collection of domain variables or greater than 0 if L consists of terms of arity greater than Arg, the value Arg indicates the selected argument of the term
Select
is a predefined variable selection method. Available methods are input_order, first_fail, anti_first_fail, smallest, largest, occurrence, anti_occurrence, most_constrained, most_constrained_per_value, least_constrained_per_value, max_regret, max_regret_lwb, min_regret_lwb, max_regret_upb, min_regret_upb, random, random(+Seed), max_weighted_degree, max_weighted_degree_per_value, min_weighted_degree, min_weighted_degree_per_value, max_activity, max_activity_per_value, min_activity, min_activity_per_value, max_weighted_degree(+WP), max_weighted_degree_per_value(+WP), min_weighted_degree(+WP), min_weighted_degree_per_value(+WP), max_activity(+AP), max_activity_per_value(+AP), min_activity(+AP), min_activity_per_value(+AP)
Choice
is the name of a predefine value choice method for choosing the value to try for a variable; Predefined choice methods are: indomain, indomain_reverse_enum, min, max, median, split, reverse_split, random, random(+Seed), interval_min, interval_max, from_smaller(P,Vals), from_larger(P,Vals), from_down(P,Vals), from_up(P,Vals)
Method
is one of the following: complete, lds(Disc), bb_min(Cost), restart_min(Cost), restart_min(Cost,Cutoff), restart_min(Cost,Cutoff,Lim), restart(Cutoff), restart(Cutoff,Lim)
Option
is a list of option terms. Currently recognized are: tiebreak(+Select), stats(+Stats), limits(+Stop), timeout(+Seconds), control(+Control), backtrack(-N), nodes(+N), ldsb_syms(+Syms)

Description

Search/6 provides an interface to gecode's search-engine, allowing search to be performed by gecode. It is designed to have the same arguments as the generic search/6 routine available for integer domain solvers. so that for common cases, the call will work for both search/6. The generic search/6 is available in the gfd_search module. The difference is that here the search is performed by gecode, and is an atomic step when viewed from ECLiPSe. In addition, this predicat support features of gecode's search engine not in generic search, such as variable selection methods based on propagation history, optimising and restart-based search methods, symmetry breaking with LDSB and searching in parallel.

The predicate perform search on the search variables in L, using the search method specified by Method, with variable and value selection methods specified by Select and Choice,respectively. For search methods that cab produce multiple solutions, backtracking into the predicate will produce the next solution if it exists. The search can be controlled further via the terms specified in Options.

In order to allow more structure in the application program, L can be a collection of compound terms rather than just domain variables. In this way all information about some entity can be easily grouped together. The terms can include items that are associated with the domain variable needed in some of the labelling methods. In addition, to allow L to reflect structures in the problem, it can be a nested collection such as a matrix.

Search methods are implmeneted by gecode's search engines. These include optimising and restart based search methods, which are not available in generic search. The optimising search methods provide some of the functionality in.lib(branch_and_bound), and is likely to be faster, but less flexible. The optimising search methods returns a single optimal solution by finding succesively better feasible solutions until no better solution can be found. If the search is terminated early, e.g. because of time-out, the best feasible solution, will be returned.

Symmetry breaking using Lightweight Dynamic Symmetry Breaking (LDSB) can be specified in the Option argument, and can be used with all search methods and most variable selection methods.

The variable selection and value choice methods are defined by gecode. They are mapped to the closest matching methods in the generic search/6 (or with a name following the same convention if the method have no correspondence). Note that except for indomain and indomain_reverse_enum, the indomain style selection methods of generic search, are not supported. Instead, most value choice methods makes a two-way choice like the methods in try_value/2. At each choice, a variable is selected, and two alternatives are created that reduces the variable's domain in complementary ways.

For source compatibility with code written for the IC and FD solvers, the generic search's indomain style method names are also accepted, but are mapped to the closest two-way choice method, e.g.indomain_min is translated to min.

For variable selection, if several entries have the same heuristic value, then a tiebreak selection method, specified by the tiebreak option term, can be used to chose from these entries.

Several of the variable selection methods makes use of one of two dynamic measurements of gecode's constraint propagation performed by the program so far: 1) Weighted degree, called AFC (accumulated failure count) in gecode; 2) Activity. These two measurements may make better variable selection in many programs because it is based on actual constraint propagation performed.

Weighted degree is a count of the number of failures so far of propagators associated with the variable. By default, the starting count is set to the number of propagator attached to the variable, to give reasonable starting values for variable selection.

Activity is a count of the number of domain reductions on the variable during propagation so far.

A decay factor (between 0 and 1) can be specified for both measure so that the count for a variable can be reduced by the Factor if it is not incremented.

The pre-defined selection methods (with the gecode name in brackets) use the following criteria:

The pre-defined choice methods (with gecode name in brackets) have the following meaning:

The different search methods are

The option list is used to pass additional parameters to and from the procedure. The currently recognized options are:

Modes and Determinism

Fail Conditions

Fails if the search engine does not find any solution. For partial search methods, this does not mean that the problem does not have a solution.

Resatisfiable

yes (non-optimising and non-restart searches)

Examples

top:-
	length(L,8),
	L :: 1..8,
	search(L,0,input_order,indomain,complete,[]).

top:-
        length(L,8),
        L::1..8,
        L = [Cost|L],
        search(L,0,input_order,indomain_max,bb_min(Cost),[]).

:- local struct(data(var,start)).
top(Ds) :-
	length(L, 8),
	L :: 1..8,
	(foreach(V, L),
 	 count(I, 1, _),
	 foreach(D, Ds) do
		D = data{var:V,start:I}
	),
	search(Ds, var of data, input_order, 
	       from_larger(start of data,Ds), complete, []).

See Also

indomain / 1, gfd_search : indomain / 2, labeling / 1, gfd_search : delete / 5, gfd_search : search / 6