Cost is the problem's cost variable: whenever we have a solution, Cost must be instantiated and represent the cost of the solution. At all other times, Cost's lower bound is a lower bound on the cost in the current state. If Cost is not updated by propagation, it can be passed as an argument into the separation goal, which can then instantiate it to the solution cost, resp. the lower bound of the cost of a branch.
Heur is the problem's heuristic variable: its lower bound is taken as an estimate for the cost that a solution derived from the current computation state might have. Like Cost, it can either be computed by propagation, or the separation goal can instantiate it explicitly for every branch. The heuristic value should always lie between the bounds of the cost variable. In the simplest case, Heur can be the same as Cost.
The Separator goal has two purposes: to detect when we have a solution, and to nondeterministically generate branches (together with their cost bound and a heuristic estimate of their quality). The separation goal has user-defined arguments, except that it must return its results in the last argument. It will be called with the instantiation state corresponding to the current search node, and should succeed once for every branch, returning:
The branching constraint descriptor I-C can have the following forms:
I-Val imposes the constraint X[I]=Val (Val is atomic) I-ge(Val) imposes lower numeric bound Val onto X[I] I-le(Val) imposes upper numeric bound Val onto X[I] I-ne(Val) imposes the constraint X[I] #\= Val I-lt(Val) imposes the constraint X[I] #< Val I-gt(Val) imposes the constraint X[I] #> Val (C1,C2) imposes conjunction of descriptor C1 and descriptor C2
% A sample separation goal. % The first argument is expected to be an Index-Variable list % of the problem variables. The separation result(s) are % returned in the last argument. The cost variable is expected % to be affected by propagation following indomain(X). separate(, true). separate(IXs, IX) :- delete(I-X, IXs, IXs1, 2, first_fail), ( nonvar(X) -> separate(IXs1, IX) ; IX=I-X, indomain(X) ). % Sample call: ?- model(XArr), ( foreacharg(X,XArr,I), foreach(I-X,IXs) do true ), bfs_minimize(XArr, Cost, Cost, separate(IXs,_)). % A separation goal that computes a more elaborate heuristic, % based on the number of remaining uninstantiated variables. separate(, _, _, true). separate(IXs, Cost, Est, IX) :- delete(I-X, IXs, IXs1, 2, first_fail), ( nonvar(X) -> separate(IXs1, Cost, Est, IX) ; IX=I-X, indomain(X), term_variables(IXs1,Vs), get_var_bounds(Cost, Lwb, Upb), Est is Upb - (Upb-Lwb)/(length(Vs)+1) ). % Sample call: ?- model(XArr), ( foreacharg(X,XArr,I), foreach(I-X,IXs) do true ), bfs_minimize(XArr, Cost, Heur, separate(IXs,Cost,Heur,_)).