[ 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
Goal
The (nondeterministic) search goal
Cost
A (usually numeric domain) variable representing the cost
Optimum
A variable which will be set to the optimum value of Cost
Options
A bb_options structure or variable

Description

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

Modules

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

Fail Conditions

Goal has no solutions

Examples

    % 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,
		    bb_options{report_success:true/0,report_failure:true/0}),
	(
	    Cost = Opt,
	    call(Goal)
	;
	    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