This module is intended to be the equivalent of Eclipse's fd_search library but extended to support real domains. (See the predicate documentation for details.) Support for drawing search trees, user defined extensions, and the SBDS library in fd_search has not been implemented in clpBNR_search.

 search(+Vars:list, +Arg:integer, +Select:atom, +Choice:atom, +Method:atom, Options:list) is nondet

Succeeds if a solution can be found for the list of Vars (numbers, constrained vars or terms containing such vars) given the search strategy specified by Method, Select, and Choice; fails otherwise. On backtracking, alternative solutions are generated. Method and Select apply uniformly to intervals of either type (real or integer. The semantics of Choice may depend on type (see below).

If a Vars list element cannot be reduced to an interval (see Arg below), it is just ignored. This means, given suitable values for the other arguments, search/6 will succeed unless no solution can be found. In addition, for continuous domains, this may result in solutions in which it can't be conclusively proven that they contain no solutions with narrower domains, due to narrowing or precision restrictions. (This may also apply to finite domains if the search Method is not complete.)

If Arg has a value N greater than 0, the 'N`th argument of elements in the Vars list will be subjects for the search; if 0 the element itself (must be an interval) is used.

Supported Method's include:

• complete: a complete search routine which explores all alternative choices.
• bbs(Steps): a bounded backtracking search allowing Steps backtracking steps.
• lds(Disc): a form of the limited discrepancy search . 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).
• dbs(Level, Method): a depth bounded search which explores the first Level choices (must be positive integer) in the search tree completely, i.e. it tries all values for the first Level selected variables. After that, it switches to search Method, which can be bbs(Steps), lds(Disc) or a integer specify the number of steps to be used in a bbs search.
• credit(Credit,Method): a credit based search that explores the top of the search tree completely. Credit (a positive integer) specifies the initial number of credits. At each choice point, the first alternative gets half of the available credit, the second alternative half of the remaining credit, and so on. When the credit run out, the system switches to another search routine specified by Method; supported methods are the same as the dbs method. Typical values for Credit are either N or N*N, where N is the number of entries in the collection. The Select argument determines the order in which the elements of Vars are selected. After one is selected and narrowed, the same criteria then is used on the remaining elements. Supported values are:
• input_order: select the first entry in the list.
• first_fail: select the entry with the smallest domain size (see below).
• anti_first_fail: select the entry with the largest domain size (see below).
• smallest: select the entry with the smallest lower bound.
• largest: select the entry with the largest upper bound.
• occurrence: select the entry with the largest number of attached constraints.
• most_constrained: select the entry with the smallest domain size. If several entries have the same domain size, select the entry with the largest number of attached constraints. The "size" of an integer interval is the number of possible values in the domain (upper bound - lower bound +1). The size of a `real is the width of the interval (upper bound - lower bound).

  The Choice argument determines how the selected interval is enumerated/split and the semantics depends on the domain type. The choice names are mapped to indomain/2 heuristics as follows:

  Choice	indomin/2 Heuristic
  indomain	enum
  indomain_min	min
  indomain_max	max
  outdomain_reverse_min	reverse_min
  outdomain_reverse_max	reverse_max
  indomain_reverse_min	reverse_min
  indomain_reverse_max	reverse_max
  indomain_middle	middle
  indomain_median	median
  indomain_split	split
  indomain_reverse_split	reverse_split
  indomain_solve	solve
  indomain_random	random
  indomain_interval	interval

  Note that many of the enumerating Choice's have no effect on real intervals. This can be helpful when searching a list of mixed integer and real domains. The effective options for real domains are indomain_middle, indomain_median, indomain_split, indomain_reverse_split, indomain_solve, indomain_random and indomain_interval. (indomain_split, indomain_reverse_split and indomain_interval are of questionable value for `real domains.)

  Options is a list of 0 or more options including:

• backtrack(-N) unifies N with the number of backtracking steps used in the search
• nodes(+N) sets an upper limit (default 2000) on the number of nodes explored in the search. If the given limit is exceeded, the search routine stops the exploration of the search tree.

 delete(?X:numeric, +Terms:list, ?Rest:list, +Arg:integer, +Select:atom) is semidet

Succeeds if X can be unified with an numeric element (number or interval) selected from the Terms list according to Select; the rest of the list is unified with Rest (includes any non-numeric). Fails if there are no numeric values in Terms or if an invalid Select method is specified. Terms may include numbers, clpBNR domain variables, or terms whose Arg argument is a number or domain variable. (Arg = 0 implies use of Vars element itself.)

Valid values of Select are documented in search/6.

 indomain(?X:numeric, +Choice:atom) is semidet

Succeeds if X (number or interval) can be narrowed or instantiated according to the heuristic specified by Choice, subject to any constraints. On backtracking alternative values are generated. Fails if the first argument is non-numeric, the heuristic is not supported, or no values can be found subject by the heuristic subject to current constraints.

For integer domains, indomain/2 will generate integer values from the domain in an order defined by the heuristic; for real domains, sub-domains will be generated by splitting at a point defined by the heuristic. In the latter case, the predicate may succeed without splitting, e.g., some heuristics may choose not to split on a point solution (middle, solve, ..).

Supported values for Choice include:

• enum: For integer domains, start enumeration from the smallest value upwards. real domains cannot be enumerated so the interval is unchanged.
• min: For integer domains, start enumeration from the smallest value upwards. On backtracking the domain is constrained to not contain the value. real domains cannot be enumerated so the domain is unchanged.
• max: For integer domains, start the enumeration from the largest value downwards. On backtracking the domain is constrained to not contain the value. real domains cannot be enumerated so the domain is unchanged.
• reverse_min: For integer domains, the domain is constrained to not contain the smallest value. On backtracking, the interval is unified with that value, i.e., values are excluded first, then assigned. Point values cannot be excluded from real domains (<, > and <> are unsound on continuous domains) so the domain is unchanged.
• reverse_max: For integer domains, the domain is constrained to not contain the largest value. On backtracking, the interval is unified with that value, i.e., values are excluded first, then assigned. See reverse_min for real domains.
• middle: For integer domains, start the enumeration from the integer closest (rounded down) to the midpoint of the domain. On backtracking, this chooses alternatively values above and below the midpoint, until all alternatives have been tested. For real domains, middle is the same as split.
• median: For integer domains, this is equivalent to middle (clpBNR domains are compact). For real domains, this is equivalent to middle except the median value of the domain is used.
• split: For integer domains, enumerate by splitting the domain successively into halves until a ground value is reached. For real domains, successively split the domain into sub-domains, favouring the lower half, until the clpBNR precision limit is reached (see small/1). (split is equivalent to splitsolve/1 on a single interval.)
• reverse_split: Like split, but tries the upper half of the domain first.
• solve: Uses clpBNR:solve to enumerate/narrow integer and real domains.
• interval: Same as split (retained for fd_search compatibility).
• random: For integer domains, enumerate in a random order. On backtracking, the previously tested value is removed. (This method uses random/1 to create random numbers, use seed/1 before to make results reproducible.) For real domains recursively split on a random point in the domain that isn't a solution until the clpBNR precision limit is reached (see small/1), favouring the lowering sub-domain on each split. On backtracking, alternatives using the upper domain sub-domain are generated. If a random split point which is not a solution cannot be found within a small number of attempts, splitting stops (like solve/1).
• Value:number: For integer domains, like middle, but start with the given Value which must be an integer. For real domains, split the domain at Value (must be in the domain) if it is not a solution generating the lower sub-interval. On backtracking the higher sub-interval is generated. If Value is a solution, the interval is not split. (Unlike many other heuristics, this is not recursively applied.)