1/* The MIT License (MIT) 2 * 3 * Copyright (c) 2024-2026 Rick Workman 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a copy 6 * of this software and associated documentation files (the "Software"), to deal 7 * in the Software without restriction, including without limitation the rights 8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9 * copies of the Software, and to permit persons to whom the Software is 10 * furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be included in all 13 * copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 21 * SOFTWARE. 22 */ 23 24/* adapted from ECLiPSe source file `generic_search.ecl` under 25 * Mozilla Public License Version 1.1 (https://www.eclipseclp.org/license/) 26 * 27 * Unsupported: 28 * Tree drawing via daVinci 29 * Hooks for user definintions 30 * Selection method `max_regret` 31 * Search methods based on ECLiPSe libraries `sbds` and GAP based `sbds` and `sbdd` 32 * `real`s are only searched using `split` and `indomain_split` using `splitsolve/1` 33 * but selection criteria (from a list) may use any "choice" or "search" methods 34 * 35 * Adds `indomain_solve`/`solve` 36 * 37 * Dependency: Uses `add_constraint/1` from v0.12.x 38 * Uses clpBNR:g_* globals abstraction for portability from v0.13.2 39 * 40 */ 41 42:- module(clpBNR_search,[ % exports: 43 search/6, % backtracking search for solutions on list of vars or like-terms 44 delete/5, 45 indomain/2 46 ]).
52:- use_module(library(lists),[flatten/2]). % for flattening search input lists 53:- use_module(library(option),[option/3]). % for option list processing 54:- use_module(library(clpBNR)). 55 56% sandboxing for SWISH 57:- multifile(sandbox:safe_global_variable/1). 58:- multifile(sandbox:safe_primitive/1). 59 60:- set_prolog_flag(optimise,true). % scoped to file/module 61 62% 63% clpBNR access support 64% 65get_size(X,0) :- number(X), !. % constants have size 0 66get_size(X,Size) :- 67 domain(X,integer(Min,Max)) -> Size is Max-Min+1; delta(X,Size). 68 69get_lwb(X,LB) :- 70 get_bounds(X,LB,_). 71 72get_upb(X,UB) :- 73 get_bounds(X,_,UB). 74 75get_bounds(X,Min,Max) :- 76 range(X,[Min,Max]). 77 78% 79% Minimal support for global var equivalent of ECLiPSe shelf create/destroy 80% Global vars are created on global stack so will be garbage collected on success 81% 82shelf_create(Shelf,Value) :- 83 gensym('$clpBNR_shelf_handle',Shelf), % new shelf handle 84 (clpBNR:g_assign(Shelf,Value) ; clpBNR:g_delete(Shelf), fail). % delete on backtracking 85% declare safe (non-ground global names) 86sandbox:safe_primitive(clpBNR_search:shelf_create(_Shelf,_Value)).
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 searchnodes(+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.140search(Vars,Arg,Select,Choice,Method,Option) :- 141 flatten(Vars, List), % flat list of Vars/Terms 142 integer(Arg), 143 callable(Select), 144 callable(Choice), 145 is_search_method(Method), 146 is_list(Option), 147 reset_backtrack_count(Option), 148 !, 149 % top-level block to handle the limited number of nodes 150 catch(search1(Method,List,Arg,Select,Choice), 151 error(domain_error(nodes,(N,Max)),_), 152 fail_error_message(clpBNR(search_nodes_failed(N,Max))) 153 ), %%search_nodes_failed(N,Max)), 154 get_backtrack_count(Option). 155search(Vars,Arg,Select,Choice,Method,Option) :- 156 fail_error_message(clpBNR(search((Vars,Arg,Select,Choice,Method,Option)))). 157 158fail_error_message(Msg) :- 159 print_message(error,Msg), 160 fail. 161 162:- multifile prolog:message//1. 163 164prologmessage(clpBNR(search(Args))) --> 165 [ "Invalid argument: search(~w).\n"-[Args] ]. 166 167prologmessage(clpBNR(search_nodes_failed(_N,Max))) --> 168 [ "Reached nodes searched limit of ~w,\n"-[Max] ]. 169 170% branch one the different search methods 171search1(complete,L,Arg,Select,Choice):- 172 labeling(L,Arg,Select,Choice). 173search1(bbs(Steps),L,Arg,Select,Choice):- 174 bbs(L,Arg,Select,Choice,Steps). 175search1(credit(Credit,Steps),L,Arg,Select,Choice):- 176 credit(L,Arg,Select,Choice,Credit,Steps). 177search1(lds(Disc),L,Arg,Select,Choice):- 178 lds(L,Arg,Select,Choice,Disc). 179search1(dbs(Level,Steps),L,Arg,Select,Choice):- 180 dbs(Level,Steps,L,Arg,Select,Choice). 181 182is_search_method(complete) :- !. 183is_search_method(bbs(N)) :- integer(N), !. 184is_search_method(credit(N,M)) :- integer(N), integer(M), !. 185is_search_method(credit(N,bbs(M))) :- integer(N), integer(M), !. 186is_search_method(credit(N,lds(M))) :- integer(N), integer(M), !. 187is_search_method(lds(N)) :- integer(N), !. 188is_search_method(dbs(N,M)) :- integer(N), integer(M), !. 189is_search_method(dbs(N,bbs(M))) :- integer(N), integer(M), !. 190is_search_method(dbs(N,lds(M))) :- integer(N), integer(M), !. 191 192% 193% different search methods 194% 195 196% labeling(+List:list, 197% ++Arg:integer, 198% ++Select:atom, 199% +Choice:atom) 200% 201labeling(Xs,Arg,Select,Choice):- 202 (delete(X,Xs,R,Arg,Select) 203 -> choose(X,Arg,Choice), 204 inc_backtrack_count, % for reporting in backtrack option 205 labeling(R,Arg,Select,Choice) 206 ; true 207 ). 208 209 210% bbs(+List:list, 211% ++Arg:integer, 212% ++Select:atom, 213% +Choice:atom, 214% ++Steps:integer) 215% same as labeling, but stops after Steps backtracking steps 216% 217bbs(L,Arg,Select,Choice,Steps):- 218 clpBNR:g_read('$clpBNR_search:backtrack', CurrentBacktracks), 219 BacktrackLimit is CurrentBacktracks+Steps, 220 clpBNR:g_assign('$clpBNR_search:backtrack_limit',BacktrackLimit), 221 catch(bbs1(L,Arg,Select,Choice),error(domain_error(backtracks,_),_),fail). 222 223bbs1(Xs,Arg,Select,Choice):- 224 (delete(X,Xs,R,Arg,Select) 225 -> choose(X,Arg,Choice), 226 inc_backtrack_count_check, 227 bbs1(R,Arg,Select,Choice) 228 ; true 229 ). 230 231 232% credit(+List:list,++Arg:integer,++Select:atom,+Choice:atom or p/2, 233% ++Credit:integer, 234% ++Extra:integer or bbs(integer) or lds(integer)) 235% same as labeling, but uses credit to control search 236% always give half the credit to the first child, 237% half of the remaining credit to the next child, etc 238 239credit([],_Arg,_Select,_Choice,_Credit,_Extra) :- !. 240credit(L,Arg,Select,Choice,Credit,Extra):- % L = [_|_], 241 credit1(Credit,Extra,L,Arg,Select,Choice). 242 243credit1(1,bbs(Extra),Xs,Arg,Select,Choice):- 244 !, 245 bbs(Xs,Arg,Select,Choice,Extra). 246credit1(1,lds(Extra),Xs,Arg,Select,Choice):- 247 !, 248 lds(Xs,Arg,Select,Choice,Extra). 249credit1(1,Extra,Xs,Arg,Select,Choice):- 250 integer(Extra), 251 !, 252 bbs(Xs,Arg,Select,Choice,Extra). 253credit1(Credit,Extra,Xs,Arg,Select,Choice):- 254 Credit > 1, 255 (delete(X,Xs,R,Arg,Select) 256 -> shelf_create(Shelf,Credit), % on backtracking, shelf destroyed 257 credit_choice(X,Arg,Choice,Shelf,Credit_child), 258 credit1(Credit_child,Extra,R,Arg,Select,Choice) 259 ; true 260 ). 261 262credit_choice(X,Arg,Choice,Shelf,Credit_child) :- 263 choose(X,Arg,Choice), 264 inc_backtrack_count, 265 distribute_credit(Shelf,Credit_child,Rest), 266 (Rest == 0 -> ! % no more credit, cut away remaining choices in choose 267 ; true 268 ). 269 270% the credit distribution 271% always give (a bit more than) half the credit to the next child 272% keep the rest of the credit for the other children 273% do not use up credit yourself 274% if credit remains, and there are no more children, the credit is lost 275% if children do not use their credit, it is lost 276distribute_credit(Shelf,Credit,Rest):- 277 clpBNR:g_read(Shelf,Old), 278 Credit is (Old+1)//2, 279 Rest is Old-Credit, 280 clpBNR:g_assign(Shelf,Rest). 281% declare safe (non-ground global names) 282sandbox:safe_primitive(clpBNR_search:distribute_credit(_Shelf,_Credit,_Rest)). 283 284 285% lds(+List:list,++Arg:integer,++Select:atom,++Choice:atom,++LDS:integer) 286% same as labeling, but only allows max LDS discrepancies against heuristic 287% solution 288% first tries 0, then 1, then 2, up to LDS discrepancies 289% 290lds(L,Arg,Select,Choice,Lds):- 291 between(0,Lds,Disc), % between(0,Lds,1,Disc), 292 lds1(L,Arg,Select,Choice,Disc). 293 294lds1(Xs,Arg,Select,Choice,Disc):- 295 (delete(X,Xs,R,Arg,Select) 296 -> (Disc==0 297 -> once(choose(X,Arg,Choice)), % allows only shallow backtracking 298 update_nodes_counter, % create new node name 299 lds1(R,Arg,Select,Choice,0) 300 ; shelf_create(Shelf,Disc), % Disc >= 1 301 lds_choice(X,Arg,Choice,Shelf,Disc1), 302 lds1(R,Arg,Select,Choice,Disc1) 303 ) 304 ; Disc == 0 % do not allow to use less than given discrepancies 305 ). 306 307lds_choice(X,Arg,Choice,Shelf,Disc) :- 308 choose(X,Arg,Choice), 309 inc_backtrack_count, 310 (dec_discrepancy(Shelf,Disc) -> true 311 ; !, % cut away remaining choices in choose 312 Disc = 0 313 ). 314 315dec_discrepancy(Shelf,Disc):- 316 clpBNR:g_read(Shelf,Disc), 317 Disc > 0, % fail if already 0 318 Disc1 is Disc - 1, 319 clpBNR:g_assign(Shelf,Disc1). 320% declare safe (non-ground global names) 321sandbox:safe_primitive(clpBNR_search:dec_discrepancy(_Shelf,_Disc)). 322 323 324% dbs(++Level:integer, 325% ++Extra:integer or bbs(integer) or lds(integer), 326% +List:list,++Arg:integer,++Select:atom,+Choice:atom) 327% 328% same as labeling, but uses depth bounded search to control search 329% explore all choice points in the first Level variables 330dbs(0,bbs(Extra),Xs,Arg,Select,Choice):- 331 !, 332 bbs(Xs,Arg,Select,Choice,Extra). 333dbs(0,lds(Extra),Xs,Arg,Select,Choice):- 334 !, 335 lds(Xs,Arg,Select,Choice,Extra). 336dbs(0,Extra,Xs,Arg,Select,Choice):- 337 integer(Extra), 338 !, 339 bbs(Xs,Arg,Select,Choice,Extra). 340dbs(Level,Extra,Xs,Arg,Select,Choice):- 341 Level >= 1, 342 (delete(X,Xs,R,Arg,Select) 343 -> choose(X,Arg,Choice), 344 inc_backtrack_count, 345 Level1 is Level-1, 346 dbs(Level1,Extra,R,Arg,Select,Choice) 347 ; true 348 ). 349 350 351% choose(?X,++Arg:integer,++Choice:atom) 352% this predicate chooses a value for the selected term 353% this choice is non-deterministic 354choose(X,N,Choice):- 355 translate_indomain_atom(Choice, Method), 356 !, % green cut?? 357 access(X,N,Var), 358 indomain(Var,Method). 359 360% Translate search/6's indomain choice atoms to those used by indomain/2 361%% no sbds or gap_* searches supported 362translate_indomain_atom(indomain, enum). 363translate_indomain_atom(indomain_min, min). 364translate_indomain_atom(indomain_max, max). 365translate_indomain_atom(outdomain_min, reverse_min). % Zinc 366translate_indomain_atom(outdomain_max, reverse_max). % Zinc 367translate_indomain_atom(indomain_reverse_min, reverse_min). 368translate_indomain_atom(indomain_reverse_max, reverse_max). 369translate_indomain_atom(indomain_middle, middle). 370translate_indomain_atom(indomain_median, median). 371translate_indomain_atom(indomain_split, split). 372translate_indomain_atom(indomain_solve, solve). 373translate_indomain_atom(indomain_reverse_split, reverse_split). 374translate_indomain_atom(indomain_interval, interval). 375translate_indomain_atom(indomain_random, random). 376 377 378% access argument N of term X, if N=0, X is returned 379access(X,0,X) :- !. % most common case? 380access(X,_,X) :- var(X), !. % var = value 381access(X,N,Var):- 382 N > 0, 383 arg(N,X,Var). 384 385 386% 387% Backtracks and Nodes support 388% 389sandbox:safe_global_variable('$clpBNR_search:node_limit'). 390sandbox:safe_global_variable('$clpBNR_search:nodes'). 391sandbox:safe_global_variable('$clpBNR_search:backtrack'). 392sandbox:safe_global_variable('$clpBNR_search:one_level'). 393sandbox:safe_global_variable('$clpBNR_search:backtrack_limit'). 394 395reset_backtrack_count(Option):- 396 option(nodes(N),Option,2000), 397 integer(N), N>=1, 398 clpBNR:g_assign('$clpBNR_search:node_limit',N), 399 clpBNR:g_assign('$clpBNR_search:nodes',0), 400 clpBNR:g_assign('$clpBNR_search:backtrack',0). 401 402get_backtrack_count(L):- 403 option(backtrack(N),L,_), % unifies var in option with backtack count 404 clpBNR:g_read('$clpBNR_search:backtrack',N). 405 406inc_backtrack_count:- 407 update_nodes_counter, 408 clpBNR:g_assign('$clpBNR_search:one_level',true). 409inc_backtrack_count:- 410 update_backtrack_count(_), 411 fail. 412 413inc_backtrack_count_check :- % only called by `bbs1` 414 update_nodes_counter, 415 clpBNR:g_assign('$clpBNR_search:one_level',true). 416inc_backtrack_count_check :- 417 update_backtrack_count(N1), 418 clpBNR:g_read('$clpBNR_search:backtrack_limit',L), % initialized by `bbs` Method 419 N1 > L, 420 domain_error(backtracks,N1). %exit_block(bbs) 421 422update_backtrack_count(N1) :- 423 clpBNR:g_read('$clpBNR_search:one_level',true), 424 clpBNR:g_assign('$clpBNR_search:one_level',false), 425 clpBNR:g_inc('$clpBNR_search:backtrack',N). 426 427update_nodes_counter:- 428 clpBNR:g_inc('$clpBNR_search:nodes',N), 429 clpBNR:g_read('$clpBNR_search:node_limit',Max), 430 (N1 >= Max 431 -> domain_error(nodes,(N1,Max)) %exit_block(nodes) 432 ; true 433 ).
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.
443% delete(-X,+List:non_empty_list,-R:list,++Arg:integer,++Select:atom) 444% choose one entry in the list based on a heuristic; this is a deterministic selection 445% a special case for input_order to speed up the selection in that case 446% Note clpBNR integer and real 447delete(X,Terms,Rest,Arg,Select) :- 448 delete1(Select,X,Terms,Rest,Arg). % reorder arguments 449 450delete1(input_order,X,List,Rest,Arg) :- !, % select in list order 451 List = [Term|Terms], 452 (delete_valid(Arg,Term) 453 -> X = Term, 454 Rest = Terms 455 ; delete1(input_order,X,Terms,Tail,Arg), 456 Rest = [Term|Tail] 457 ). 458delete1(Select,X,List,Rest,Arg) :- % select based on criterion 459 (memberchk(Select, % rest of supported values ... 460[first_fail, anti_first_fail, smallest, largest, occurrence, most_constrained] 461 ) 462 -> NaN is nan, 463 (Select == most_constrained -> Crit = crit(NaN,NaN) ; Crit = NaN), 464 find_best_and_rest(List,Crit,_,X,Rest/Rest,Arg,Select), % scan for best 465 delete_valid(Arg,X) % ensure numeric 466 ; fail_error_message(clpBNR(delete_method(Select))) 467 ). 468 469prologmessage(clpBNR(delete_method(Select))) --> 470 [ "Invalid Select method: ~w .\n"-[Select] ]. 471 472delete_valid(0,X) :- !, 473 (number(X) -> true ; interval(X)). 474delete_valid(Arg,X) :- 475 compound(X), 476 Arg > 0, 477 arg(Arg,X,Val), 478 delete_valid(0,Val). 479 480find_best_and_rest([], _CritOld, BestTerm, BestTerm, _Rest/[], _Arg, _Select) :- !. 481find_best_and_rest([Term|Terms], CritOld, BestTerm, X, Rest/Tail, Arg, Select) :- 482 access(Term,Arg,Var), access(BestTerm,Arg,BestVal), 483 (number(Var) % pick constants and stop 484 -> X = Term, 485 (interval(BestVal) -> Tail = [BestTerm|Terms] ; Tail = Terms) 486 ; find_value(Select,Var,CritNew), 487 (better_item(CritNew,CritOld) % better than the old one ? 488 -> (interval(BestVal) -> Tail = [BestTerm|NxtTail] ; NxtTail = Tail), % put interval(Best) in Rest 489 find_best_and_rest(Terms, CritNew, Term, X, Rest/NxtTail, Arg, Select) 490 ; Tail = [Term|NxtTail], % put Term in Rest 491 find_best_and_rest(Terms, CritOld, BestTerm, X, Rest/NxtTail, Arg, Select) 492 ) 493 ). 494 495better_item(crit(SizeNew,NumberNew),crit(SizeOld,NumberOld)) :- % most_constrained 496 (better_item(SizeNew,SizeOld) 497 -> true 498 ; better_item(NumberNew,NumberOld) 499 ). 500better_item(CritNew,CritOld) :- number(CritNew), number(CritOld), 501 (CritNew is nan 502 -> fail % nan is never better 503 ; (CritOld is nan 504 -> true % non-nan is better than nan 505 ; CritNew < CritOld) % othewise less is better 506 ). 507 508% find_value(++Select:atom,?X:dvarint, 509% -Crit:number or crit(number,number)) 510% 511% Find a heuristic value from a domain variable: the smaller, the better. 512% Values will be compared using @<, so be aware of standard term ordering! 513% If the Criterion remains uninstantiated, this indicates an optimal value, 514% which will be picked without looking any further down the list. 515% Note: should work for clpBNR integer and real intervals 516find_value(first_fail,X,Size) :- 517 get_size(X,Size), !. 518find_value(anti_first_fail,X,Number) :- !, 519 get_size(X,Size), !, % can be 1.0Inf 520 Number is -Size. % -1.0Inf @< -99 521find_value(smallest,X,Min) :- 522 get_lwb(X,Min), !. 523find_value(largest,X,Number) :- 524 get_upb(X,Max), !, 525 Number is -Max. 526find_value(occurrence,X,Number) :- 527 interval_degree(X,Nr), !, % constants have degree 0, cheap op for clpBNR) 528 Number is -Nr. 529find_value(most_constrained,X,crit(Size,Number)) :- 530 find_value(first_fail,X,Size), 531 find_value(occurrence,X,Number), 532 !. 533find_value(_Select,_X,Crit) :- 534 Crit is nan. % invalid X, Crit = nan
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.)560% indomain(?X:dvarint,++Method:atomic) 561% IndomainType is either one of min, max, middle or an integer 562% these indomain versions remove the previous value on backtracking 563% Note: only assigns values to finite domain (i.e., clpBNR integer) variables 564indomain(X,Method):- 565 domain_type(X,Type) -> indomain1(Method,X,Type) ; number(X). 566 567domain_type(X,Type) :- 568 domain(X,D), % fails if not an interval 569 (D==boolean -> Type=integer ; functor(D,Type,2)). % D=Type(_,_). 570 571indomain1(enum,X,Type) :- !, 572 indomain_enum(Type,X). 573indomain1(min,X,Type) :- !, 574 get_lwb(X,Min), 575 indomain_min(Type,X,Min). 576indomain1(max,X,Type):- !, 577 get_upb(X,Max), 578 indomain_max(Type,X,Max). 579indomain1(reverse_min,X,Type) :- !, 580 get_lwb(X,Min), 581 outdomain_min(Type,X,Min). 582indomain1(reverse_max,X,Type) :- !, 583 get_upb(X,Max), 584 outdomain_max(Type,X,Max). 585indomain1(middle,X,Type) :- !, 586 indomain_middle(Type,X). 587indomain1(median,X,Type) :- !, 588 indomain_median(Type,X). 589indomain1(split,X,Type) :- !, 590 indomain_split(Type,X). 591indomain1(reverse_split,X,Type) :- !, 592 indomain_reverse_split(Type,X). 593indomain1(solve,X,_Type) :- !, 594 solve(X). 595indomain1(interval,X,Type) :- !, % clpBNR intervals are compact (no gaps), so use split 596 indomain_split(Type,X). 597indomain1(random,X,Type) :- !, 598 indomain_random(Type,X). 599indomain1(Value,X,integer):- !, 600 integer(Value), 601 get_bounds(X,Min,Max), 602 ( Value =< Min -> 603 % if the starting value is too small, use indomain_min 604 indomain_min(integer,X,Min) 605 ; Value >= Max -> 606 % if the starting value is too large, use indomain_max 607 indomain_max(integer,X,Max) 608 ; % enumerate from a starting value inside the domain 609 % From fd_search: is this enough in all cases ?? 610 Range is 2*max(Max-Value,Value-Min)+1, 611 indomain_from(X,Value,1,Range) 612 ). 613indomain1(Value,X,real):- 614 number(Value), 615 get_bounds(X,Min,Max), 616 ( (Min >= Value ; Value >=Max) 617 -> fail % Value not in domain, cannot do anything 618 ; % if Value is not a solution split the domain if not a solution 619 (\+(X=Value) 620 -> (add_constraint(X =< Value) ; add_constraint(Value =< X)) 621 ; true % Value is in domain, can't split real on this value 622 ) 623 ). 624 625indomain_enum(integer,X) :- 626 enumerate(X). 627indomain_enum(real,_X). % enumeration of real - succeed with no narrowing or choicepoint 628 629% indomain_min(?X:dvar, ++Value:integer) 630% the choice consists in either taking the proposed value or in excluding it 631% and choosing another one 632indomain_min(integer,X,X). 633indomain_min(integer,X,Min):- % if integer, can remove current lb 634 add_constraint(X > Min), 635 get_lwb(X,New), 636 indomain_min(integer,X,New). 637indomain_min(real,_X,_Min). % if real, can't narrow further 638 639outdomain_min(integer,X,Min):- 640 add_constraint(X > Min), 641 get_lwb(X,New), 642 outdomain_min(integer,X,New). 643outdomain_min(integer,X,X). 644outdomain_min(real,_X,_Min). 645 646% indomain_max(?X:dvar, ++Value:integer) 647% the choice consists in either taking the proposed value or in excluding it 648% and choosing another one 649indomain_max(integer,X,X). 650indomain_max(integer,X,Max):- % if integer, can remove current ub 651 add_constraint(X < Max), 652 get_upb(X,New), 653 indomain_max(integer,X,New). 654indomain_max(real,_X,_Max). % if real, can't narrow further 655 656outdomain_max(integer,X,Max):- 657 add_constraint(X < Max), 658 get_upb(X,New), 659 outdomain_max(integer,X,New). 660outdomain_max(integer,X,X). 661outdomain_max(real,_X,_Max). 662 663indomain_middle(integer,X) :- 664 get_bounds(X,Min,Max), 665 Value is (Min+Max)//2, % default rounds toward 0, different from split 666 indomain1(Value,X,integer). % alternating around value 667indomain_middle(real,X) :- % same as splitsolve on single var 668 (small(X) 669 -> true % small, don't split further 670 ; midpoint(X,Middle), % split at midpoint 671 ( add_constraint(X =< Middle) ; add_constraint(Middle =< X) ), 672 indomain_middle(real,X) 673 ). 674 675indomain_median(integer,X) :- % same as middle for integers (intervals are compact) 676 indomain_middle(integer,X). 677indomain_median(real,X) :- 678 (small(X) 679 -> true % small, don't split further 680 ; median(X,Median), % split at median 681 (add_constraint(X =< Median) ; add_constraint(Median =< X) ), 682 indomain_median(real,X) 683 ). 684 685% split the domain until only an integer value is left or real interval sufficiently narrow 686indomain_split(_Type,X):- 687 number(X), 688 !. 689indomain_split(integer,X):- 690 get_bounds(X,Min,Max), 691 Middle is (Min+Max) div 2, % Note rounds toward -inf, different definition of middle 692 ( add_constraint(X =< Middle) ; add_constraint(Middle < X) ), 693 indomain_split(integer,X). 694indomain_split(real,X):- 695 indomain_middle(real,X). 696 697indomain_reverse_split(integer,X):- 698 integer(X), 699 !. 700indomain_reverse_split(integer,X):- 701 get_bounds(X,Min,Max), 702 Middle is (Min+Max) div 2, % Note rounds toward -inf, different definition of middle 703 ( add_constraint(X > Middle) ; add_constraint(Middle >= X) ), 704 indomain_reverse_split(integer,X). 705indomain_reverse_split(real,X):- 706 (small(X) 707 -> true % don't split further 708 ; midpoint(X,Middle), 709 ( add_constraint(X >= Middle) ; add_constraint(Middle >= X) ), 710 indomain_reverse_split(real,X) 711 ). 712 713% choose values from the domain at random; on backtracking, the previous value 714% is removed, so that it can be used for a complete enumeration 715indomain_random(Type,X):- 716 random_value(Type,X,Try), 717 indomain_random(Type,X,Try). 718 719random_value(integer,X,Try) :- 720 get_bounds(X,Min,Max), 721 Try is Min+random(Max-Min+1). % random:random_between/3 722random_value(real,X,Try) :- 723 get_bounds(X,Min,Max), 724 Try is Min+random_float*(Max-Min). 725 726indomain_random(integer,X,X). 727indomain_random(integer,X,Try):- 728 add_constraint(X <> Try), 729 indomain_random(integer,X). 730indomain_random(real,X,Try) :- 731 split_random(10,X,Try). % try up to 10 random values for non-solution 732 733split_random(0,_X,_Try) :- !. % stop, failed to find splittable point 734split_random(_Ct,X,_Try) :- 735 small(X), !. % stop, too small to split 736split_random(Ct,X,Try) :- 737 (\+(X = Try) % split on non-solution 738 -> ( add_constraint(X =< Try) ; add_constraint(Try =< X) ), 739 indomain_random(real,X) % rinse and repeat 740 ; random_value(real,X,NxtTry), % can't split on this Value, try another 741 NxtCt is Ct-1, % decrement Ct 742 split_random(NxtCt,X,NxtTry) % rinse and repeat 743 ). 744 745% indomain_from(?X:dvar, ++Value:integer, ++Inc:integer, ++Range:integer) 746% the choice consists in either taking the proposed value or in excluding it 747% and choosing another one 748% the next value is always the old value plus the increment 749% the next increment is one bigger than the previous, but of opposite sign 750% 1, -2, 3, -4, 5, -6, 7 ... 751% if the increment becomes too large, you can stop 752indomain_from(X,X,_,_). 753indomain_from(X,Value,Inc,Range):- 754 add_constraint(X
clpBNR_search: Support for alternative search strategies based on ECLiPSe family of search libraries
This module is intended to be the equivalent of ECLiPSe's fd_search library but extended to support
realdomains. (See the predicate documentation for details.) Support for drawing search trees, user defined extensions, and the SBDS library infd_searchhas not been implemented inclpBNR_search.