[ library(branch_and_bound) | Reference Manual | Alphabetic Index ]

bb_min_cost(+Goal, ?Cost, -Optimum, +Options)

Find the minimal cost using the branch-and-bound method
The (nondeterministic) search goal
A (usually numeric domain) variable representing the cost
A variable which will be set to the optimum value of Cost
A bb_options structure or variable


Determines the minimum possible value that the variable Cost can attain in any solution of Goal. This value is returned as Optimum. Neither Cost nor any variable in Goal is instantiated. The predicate is useful when one is interested in sub-optimal solutions, see example.

This predicate can be defined as

	bb_min_cost(Goal, Cost, Optimum, Options) :-
		bb_min(Goal, Cost, [], _, Optimum, Options).
Options are interpreted in the same way as for bb_min/6 (the solutions-parameter is ignored).

Modes and Determinism


This predicate is sensitive to its module context (tool predicate, see @/2).

Fail Conditions

Goal has no solutions


    % A predicate to enumerate solutions in increasing cost order
    :- lib(ic).
    :- lib(branch_and_bound).

    ic_increasing_cost(Goal, Cost) :-
    	bb_min_cost(Goal, Cost, Opt,
	    Cost = Opt,
	    Cost #> Opt,
	    ic_increasing_cost(Goal, Cost)

    % sample run:
    ?- ic_increasing_cost(member(C-X,[9-a,4-b,2-c,4-d]), C).
    C = 2
    X = c
    Yes (0.00s cpu, solution 1, maybe more) ? ;
    C = 4
    X = b
    Yes (0.00s cpu, solution 2, maybe more) ? ;
    C = 4
    X = d
    Yes (0.00s cpu, solution 3, maybe more) ? ;
    C = 9
    X = a
    Yes (0.00s cpu, solution 4, maybe more) ? ;
    No (0.00s cpu)

See Also

bb_min / 3, bb_min / 6