[ 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:
- input_order (INT_VAR_NONE) the first entry in the list is selected
- random (INT_VAR_RND) an entry is selected at random.
- random(+Seed) (INT_VAR_RND) an entry is selected at random,
with the random seed Seed. Seed is a non-negative integer.
- anti_occurrence (INT_VAR_DEGREE_MIN) the entry whose corresponding gecode variable with the
smallest number of attached propagators is selected
- occurrence (INT_VAR_DEGREE_MAX) the entry whose corresponding gecode variable with the
largest number of attached propagators is selected
- max_weighted_degree max_weighted_degree(+WDParams) (INT_VAR_AFC_MAX)
the entry with the largest weighted degree is selected. The optional WDParams
argument is a list of parameters for initialising the weighted degree.
- max_weighted_degree_per_value max_weighted_degree_per_value(+WDParams)
(INT_VAR_AFC_SIZE_MIN) the entry with the smallest weighted degree divided by
domain size is selected. The optional WDParams argument is a list of
parameters for initialising the weighted degree. The parameters are:
- 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).
- min_weighted_degree min_weighted_degree(+WDParams) (INT_VAR_AFC_MIN) the entry with the smallest
weighted degree is selected. The optional WDParams
argument is a list of parameters for initialising the weighted degree.
- min_weighted_degree_per_value min_weighted_degree_per_value(+WDParams)
(INT_VAR_AFC_SIZE_MAX) the entry with the largest weighted degree divided by
domain size is selected. The optional WDParams
argument is a list of parameters for initialising the weighted degree.
- max_activity max_activity(+AParams) (INT_VAR_ACTIVITY_MAX) the entry with the
largest activity is selected. Activity for a variable Activity is a
measure of how much that variable was involved in constraint
propagation. Note that activity is maintained by gecode's search engine
for the search variables, and is not available outside.
The parameters are:
- decay(Decay) specify the decay factor (number between
0 and 1, where 1 is no decay). Default is 1.
- 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.
- none no initialisation (default)
- max_activity_per_value max_activity_per_value(+AParams) (INT_VAR_ACTIVITY_SIZE_MAX) the entry with the
largest activity divided by domain size is selected.
- min_activity min_activity(+AParams) (INT_VAR_ACTIVITY_MIN) the entry with the
smallest activity is selected.
- min_activity_per_value min_activity_per_value(+AParams) (INT_VAR_ACTIVITY_SIZE_MIN) the entry with the
smallest activity divided by domain size is selected.
- smallest (INT_VAR_MIN_MIN) the entry with the smallest value in the domain is selected
- smallest_upb (INT_VAR_MAX_MIN) the entry with the smallest
upper bound in the domain is selected
- largest_lwb (INT_VAR_MIN_MAX) the entry with the largest lower
bound in the domain is selected
- largest (INT_VAR_MAX_MAX) the entry with the largest value in the domain is selected
- first_fail (INT_VAR_SIZE_MIN) the entry with the smallest domain size is selected
- anti_first_fail (INT_VAR_SIZE_MAX) the entry with the largest domain size is selected
- least_constrained_per_value (INT_VAR_DEGREE_SIZE_MAX) the entry with the largest number of attached propagators divided by domain size.
- most_constrained_per_value (INT_VAR_DEGREE_SIZE_MIN) the entry with the smallest
number of attached propagators divided by the domain size.
- min_regret_lwb (INT_VAR_REGRET_MIN_MIN) the entry with the smallest difference between the
smallest and second smallest value in the domain is selected.
- max_regret (INT_VAR_REGRET_MIN_MAX) the entry with the largest difference between the
smallest and second smallest value in the domain is selected. This method is
typically used if the variable represents a cost, and we are interested in the
choice which could increase overall cost the most if the best possibility is
not taken. Unfortunately, the implementation sometimes does not always
work. If two decision variables incur the same minimal cost, the regret is not
calculated as zero, but as the difference from this minimal value to the next
greater value. Note this is an alias for max_regret_lwb
- max_regret_lwb (INT_VAR_REGRET_MIN_MAX) is an alias to max_regret.
- min_regret_upb (INT_VAR_REGRET_MAX_MIN) the entry with the smallest difference between the
largest and second largest value in the domain is selected.
- max_regret_upb (INT_VAR_REGRET_MAX_MAX) the entry with the largest difference between the
largest and second largest value in the domain is selected.
- most_constrained (INT_VAR_SIZE_MIN, INT_VAR_DEGREE_MAX) the entry with the smallest domain size is
selected. If several entries have the same domain size, the entry with the
largest number of attached constraints is selected. This is provided for
compatibility, as this define a tiebreak method (occurrence). Any tiebreak
method defined in options is ignored.
The pre-defined choice methods (with gecode name in brackets) have the following meaning:
- indomain (INT_VALUES_MIN)
Values are tried in increasing order.
- indomain_reverse_enum (INT_VALUES_MAX)
Values are tried in decreasing order.
- min (INT_VAL_MIN)
Minimum value in the domain (alias: indomain_min).
- max (INT_VAL_MAX)
Maximum value in the domain (alias: indomain_max).
- median(INT_VAL_MED)
Median value of the domain Note median is defined differently from IC (alias: indomain_median).
- random (INT_VAL_RND)
Random element in the domain is selected (alias: indomain_random).
- random(+Seed) (INT_VAL_RND)
Random element in the domain is selected The random sequence is
initialised with seed Seed, which is a non-negative integer.
- split (INT_VAL_SPLIT_MIN)
try first the lower domain half, then the upper (alias: indomain_split).
- reverse_split (INT_VAL_SPLIT_MAX)
try first the upper domain half, then the lower
(alias: indomain_reverse_split).
- interval_min (INT_VAL_RANGE_MIN)
If the domain consists of several intervals, chose the smallest interval.
For one interval, split is used.
(alias: indomain_interval)
- interval_max (INT_VAL_RANGE_MAX)
If the domain consists of several intervals, chose the largest interval.
the interval, choosing the largest interval. For one interval,
reverse_split is used
- from_larger(+Pos,+Suggestions) (INT_VAL_NEAR_MAX)
Suggestions is a collection containing suggested values, one for each search
variable. For each variable, pick the domain value nearest its
corresponding suggested value. If there is a tie, chose the larger
value.
If Pos is 0, then Suggestions is a collection of values. If Pos > 0,
then Suggestions is a collection of structures, with the suggested
value in the Pos'th argument of the structure. The idea is that the same
structure can be used to store both the variable and its suggested
value, e.g. as a pair Var-2.
- from_smaller(+Pos,+Suggestions) (INT_VAL_NEAR_MAX)
similar to from_larger, except chose the smaller value if there is a tie.
- from_down(+Pos,+Suggestions) (INT_VAL_NEAR_DEC)
similar to from_larger, except chose values smaller than the suggested
value first.
- from_up(+Pos,+Suggestions) (INT_VAL_NEAR_INCC)
similar go from_down, except chose values larger than its suggested
value first.
The different search methods are
- complete (DFS)
a complete search routine which explores all alternative choices.
Alternative solutions are returned on backtracking
- lds(Disc) (LDS)
A form of the limited discrepancy search . Disc is a
non-negative integer. This method iteratively tries 0, 1, 2 .. Disc
changes against the heuristic (first) value. Typical values are
between 1 and 3 (which already may create too many alternatives for
large problems). Note that suggested fitst values for variables cam
be provided by the from_* value choice methods.
- bb_min(Cost) (BAB)
Branch-and-bound search to find the minimal value for the cost variable Cost.
This should be a domain variable that is instantiated at the end of the
search. The search will return an optimal solution, unless terminated early,
in which case, the best solution found (if there is one) is returned. If Cost
variable is not instantiated at the end of the search, the search is aborted.
This provide some of the functionality of branch-and-bound search in
lib(branch_and_bound), but is less flexible (no user defined search) but is
likely to be faster. Will only return one optimal solution.
- restart(+Cutoff [,+Nogoodslim]) (RBS with DFS)
Restart search will restart the search when the number of nodes searched
exceeds the cutoff threshold. The threshold can change with successive
restart, and is specified by Cutoff. Nogoodslim is an optional argument, which
if supplied, nogoods learning will be performed during the search, and
no-good constraints learned from the old search are posted before restarting
the search.
Cutoff specifies the cutoff threshold sequence. The following are available:
- geo(+S, +Base)
Geometric cutoff with a scale factor S and base Base (both
non-negative integers). The cutoff thresholds are defined by
S*(Base^N), where N is the Nth restart.
- luby(+S)
the cutoff sequence is based on the Luby sequence, multiplied by
the scale factor S (non-negative integer). The Luby sequence
is a sequence of restart thresholds suggested by Luby and
others in 1993.
- random(+Min,+Max,+N,+Seed)
the cutoff value is chosen randomly between Min and
Max, with only N+1 values distributed evenly in the range
are available for selection, to make sure that values chosen
are significantly different from each other.
- con(+C)
the same cutoff value C (positive integer) is used for all restarts.
- lin(+S)
The cutoff value is increased by S (positive integer) for
each restart.
Nogoodslim (non-negative integer) specifies the depth limit in the search-tree to which no-goods will be learned. Setting this to 0 (zero) is the same as not
using no-goods.
- restart_min(Cost [,+Cutoff [,+Nogoodslim]]) (RBS with BAB)
Branch-and-bound search as in bb_min, but the search is restarted after finding
a new solution and imposing the new bound. Optionally, if Cutoff is supplied,
the search will also restart when the number of nodes searched exceed the given
Cutoff. An additional optional argument NogoodsLim can also be supplied that
will use no-good learning.
The option list is used to pass additional parameters to and from the
procedure. The currently recognized options are:
- tiebreak(+Selection)
Selection is one of the variable selection methods, and is used as a tie-break
if the primary selection method yields more than one candidate. Obviously not
all combinations of selection methods makes sense (e.g. it should not be the
same as the primary), but no check is done, they are simply passed to gecode.
- stats(+Stats)
Stats is a named gfd_stats structure, defined as:
:- export struct(gfd_stats(prop,fail,node,depth,mem)).
The fields of the structure should be uninstantiated, and the search predicate
will instantiate the fields with statistics obtained from gecode for the search:
prop for the number of propagations, fail for the number of failed nodes,
node for number of nodes expanded, depth for maximum depth of search stack,
mem for peak memory allocated (in bytes).
- timeout(+Seconds)
Specify the number of seconds that the search will be performed before it is
terminated. Seconds can be a real or integer number, and 0 means there is
no timeout. For multi-solution search, the timer is reset each time a
new solution is obtained. For optimising search, the best feasible
solution found so far, if any, is returned.
- limits(+Stats)
Specify limits to stop the search. Stats is the same gfd_stats struct used for
obtaining statistics. To specify a limit for a particular statistics, the
corresponding field should be instantiated to the limit. Only the prop, node,
fail and mem fields are significant. Entries in the other fields are ignored.
For optimising search, the best feasible solution found so far, if any, is
returned.
- control(+Control)
Control is a named gfd_control structure, defined as:
:- export struct(gfd_control(commit_distance,adaptive_distance,threads)).
This is used to pass information to gecode to control the search. The
corresponding field should be instantiated to the value passed to gecode.
threads may be of most interest as if threads is set to a value >= 2,
this will allow parallel search. See the gecode manual for more
details on the options.
- backtrack(-N)
Provided for compatibility with generic search/6. Returns the number of fail
nodes (fail field of statistics.
- nodes(++N)
Provided for compatibility with generic search/6. Equivalent to setting the
node field of limits. The node field will be unified with N
- ldsb_syms(+Syms)
Use Lightweight Dynamic Symmetry Breaking (LDSB) to reduce the search-space.
The symmetries for the problem are specified in Syms, which is a list of
symmetry specifications. The syntax for the symmetry specifications are
compatible with the ones used in ip{ldsb_initialise/2} of lib(ldsb),
the LDSB library for IC.
Some of the symmetry specifications expect a matrix of NRows rows by NCols
columns. Such an argument should be supplied as a 2-D collection, i.e.
either as a Matrix M with dimensions dim(M, [NRows,NCols]),
or a list of NRows lists, where the sub-lists are all the same length of NCols
items.
Some of the symmetry specifications can be applied to all the search variables
(i.e. the first argument (L) of the predicate), or to a subset.
For such specifications, if the specification includes a collection of
variables, these will be used; otherwise it is applied to all search variables.
Note that the same form is expected for variables given with the specification
and those in L, i.e. the variables will be in the same Arg'th position
of the items in the collection given for L and in any symmetry
specifications.
The following are available:
- value_interchange(+Vars) specifies that the variables in collection
Vars are interchangeable.
- variable_interchange(++Vals) specifies that the values in collection
Vals are interchangeable.
- variables_interchange specifies that all search variables are
interchangeable.
- parallel_variable_interchange(+Vars) Vars is a 2-D collection of
search variables. This specifies that the variables
in the sub-list or sub-vector are interchangeable, e.g.
parallel_variable_interchange([]([](A,B),[](C,D),[](E,F))) says that the
sequence A-B can be interchanged with the sequence C-D and E-F.
- parallel_value_interchange(++Vals) Vals is a 2-D collection of
values. This specifies that the value sequences in each sub-vector or sub-list
in Vals are interchangeable.
- value_reflection(+L,+U) specifies the values L..U can be reflected,
i.e. vale L+i maps to U-1.
- rows_interchange rows_interchange(+MatVars) specifies that
the rows of the matrix is interchangeable. The matrix is either given
in MatVars, or is all the search variables (L), and must be in
matrix form.
- columns_interchange columns_interchange(+MatVars) specifies that
the columns of matrix are interchangeable. The matrix is either given in
MatVars, or is all the search variables L, and must be
in matrix form.
- row_reflection rows_reflection(+MatVars) specifies that the rows
of the matrix can be reflected around their centre. The matrix is either given in MatVars, or is all the search variables L), and must be
in matrix form.
- column_reflection columns_reflection(+MatVars) specifies that the columns
of the matrix can be reflected around their centre. The matrix must be
a square matrix, and can be either given in MatVars, or is all the search variables (L), and must be
in matrix form.
- diagonal_reflection diagonal_reflection(+MatVars) specifies that the
variables of the matrix can be reflected around the main diagonal of the
matrix. The matrix must be a square matrix, and is either given in MatVars, or is all the search
variables (L), and must be in matrix form.
Modes and Determinism
- search(+, ++, ++, +, ++, +) is nondet
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