[ library(branch_and_bound) | The ECLiPSe Libraries | Reference Manual | Alphabetic Index ]
bb_min(+Goal, ?Cost, ?Template, ?Solution, ?Optimum, ?Options)
Find a minimal solution using the branch-and-bound method
- Goal
- The (nondeterministic) search goal
- Cost
- A (usually numeric domain) variable representing the cost
- Template
- A term containing all or some problem variables
- Solution
- A term which will be unified with the optimized Template
- Optimum
- A variable which will be set to the optimum value of Cost
- Options
- A bb_options structure or variable
Description
A solution of the goal Goal is found that minimizes
the value of Cost. Cost should be a
variable that is affected, and eventually instantiated, by
Goal. Usually, Goal is the search procedure
of a constraint problem and Cost is the variable
representing the cost. The solution is found using the branch
and bound method: as soon as a solution is found, it gets
remembered and the search is continued or restarted with an
additional constraint on the Cost variable which
requires the next solution to be better than the previous one.
Iterating this process yields an optimal solution in the end.
The possible options are
- strategy:
-
- continue (default)
- after finding a solution, continue
search with the newly found bound imposed on Cost
- restart
- after finding a solution, restart the whole
search with the newly found bound imposed on Cost
- step
- a synonym for 'restart'
- dichotomic
- after finding a solution, split the
remaining cost range and restart search to find a solution
in the lower sub-range. If that fails, assume the upper
sub-range as the remaining cost range and split again.
The new bound or the split point, respectively, are computed
from the current best solution, while taking into account the
parameters delta and factor.
- from:
- number - an initial lower bound for the cost (default -1.0Inf)
- to:
- number - an initial upper bound for the cost (default +1.0Inf)
- delta:
- number - minimal absolute improvement required for each step
(default 1.0), applies to all strategies
- factor:
- number - minimal improvement ratio (with respect to the lower
cost bound) for strategies 'continue' and 'restart' (default 1.0),
or split factor for strategy 'dichotomic' (default 0.5)
- timeout:
- number - maximum seconds of cpu time to spend (default: no limit)
- report_success:
- GoalPrefix - an atom (predicate name) or structure (goal prefix),
specifying a goal to be invoked whenever the branch-and-bound
process finds a better solution. The invoked goal is constructed
by adding three arguments (Cost, Handle, Module) to GoalPrefix.
Cost is a float number representing the cost of the solution found,
Handle is a handle as accepted by bb_cost/2 or bb_solution/2,
and Module is the context module of the minimisation.
The default handler prints a message.
- report_failure:
- GoalPrefix - an atom (predicate name) or structure (goal prefix),
specifying a goal to be invoked whenever the branch-and-bound
process cannot find a solution in a cost range. The invoked goal
is constructed by adding three arguments (Cost, Handle, Module) to
GoalPrefix. Cost is a From..To structure representing the range
of cost in which no solution could be found, Handle is a handle
as accepted by bb_cost/2 or bb_solution/2, and Module is the
context module of the minimisation.
The default handler prints a message.
The default options can be selected by passing a free variable as
the Options-argument. To specify other options, pass a bb_options-
structure in with-syntax, e.g.
bb_options with [strategy:dichotomic, timeout:60]
In order to maximize instead of minimizing, introduce a negated
cost variable in your model and minimize that instead.
Unlike bb_min/3, bb_min/6 does not affect Goal or Cost after
the optimum has been found. Instead, the optimum cost value is returned
in Optimum, and the Solution argument gets unified with an instance of
Template where the variables have the values that correspond to the
optimal solution. Note that bb_min/3 is actually based on bb_min/6
and can be defined as:
bb_min(Goal, Cost, Options) :-
bb_min(Goal, Cost, Goal, Goal, Cost, Options).
Compatibility note: For backward compatibility, the report_success and
report_failure options also accept Name/Arity specifications with
maximum arity 3 for the handler goals. The three optional arguments
are then Cost, Handle, and Module.
See Also
bb_min / 3