bfs_minimize(?Vars, ?Cost, ?Heur, ?Separator)

Vars

Array of problem variables

Cost

Cost variable

Heur

Heuristic variable

Separator

Separator goal

Description

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:

true

iff the node is already a solution without further branching. Cost must then be instantiated to the solution's cost. Heur is ignored in this case and can remain undefined.

I-C

for a branch that imposes constraint C onto variable X[I]. Cost must have a lower bound corresponding to this choice, and Heur must a have a lower bound (or be instantiated to) a heuristics estimate for a solution cost that this branch could lead to. Heur should lie between the cost lower and upper bounds (if it is outside, it will be rounded into this interval).

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

Modules

Examples

    % 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,_)).