Re: min_max and minimize

Hi Farouk,

Firstly I'll put in a "plug" for the new generic
branch and bound library
lib(branch_and_bound)
which we recommend you use for optimisation whether you have loaded 
lib(fd) or lib(ic) or neither!

Broadly min_max and minimize are subsumed by the new generic branch and bound library predicate
bb_min/3.

bb_min(+Goal,?Cost,?Options)
allows you to specify different options for controlling the search.
The default option is run when you call
branch_and_bound:minimize(Goal,Cost)
which is equivalent to
bb_min(Goal,Min,_)
which is equivalent to
bb_min(Goal,Min, bb_options with strategy:continue)

This is precisely the same strategy that is used by the predicate
fd:minimize(Goal,Min)
in the fd library.

An alternative strategy, for bb_min is:
bb_min(Goal,Min, bb_options with strategy:step)
This is the same strategy used by the fd predicate
fd:min_max(Goal,Min)

The difference between the strategies is explained in the documentation.
The 'continue' strategy, used by minimize, after finding a solution continues
to explore the search tree from that point (as if the search had failed at the 
leaf node associated with the solution).  
The 'step' strategy, used by min_max, restarts the search after finding each solution.
The new upper bound on the minimum is posted at the root of the new search tree, which typically
changes the variable selection strategy and thus changes the shape of the 
search tree.

If the new upper bound was only used passively, so the search followed the same path as before,
except for failing at nodes cut off by the new bound, then the 'step' strategy would be less
efficient than the 'continue' strategy (since it would simply reexplore
the same parts of the search space already explored while finding the previous solution).
However for many problems, the new bound changes the search behaviour so that it goes more directly
towards a new improved solution.  In this way, surprisingly, it can often outperform the 'continue'
strategy.
 
	Cheers
		Mark



-- 
_______________________________________________________________
Dr. Mark Wallace, IC-Parc,		Phone  +44 (0)20 7594 8434 
William Penney Laboratory, 		Fax    +44 (0)20 7594 8432
Imperial College, London SW7 2AZ, UK.	Email: mgw@icparc.ic.ac.uk