[gecode-users] nested cost functions

[revo revo]

Thanks. One thing I'm confused by is that in talking to fellow colleagues,
they say that branch and bound isn't related to constraint programming. But
from the manual and Schulte's "Programming Constraint Inference Engines", it
seems like a best solution search using BAB is one form of constraint
programming.

Maybe if someone could direct me towards a tutorial that sharpens the
distinction between best solution search CP and optimization and how BAB
fits into gecode's CP framework (I thought I understood it as a search
technique, but now I'm being told it's unrelated to CP), I would be
enlightened.

~r



On Wed, Sep 14, 2011 at 7:21 AM, Mikael Zayenz Lagerkvist
<zayenz at gmail.com>wrote:

> On 09/14/2011 12:20 PM, revo revo wrote:
>
>> One additional question - for some reason when I use DFS, I am able to
>> return all solutions, but when I use BAB, I seem to only get one solution,
>> using the exact same Script class (with no other differences to how it's
>> called). Any reason for this?
>>
>
> The following is assuming that you let the program explore all of the
> search space in both runs. If you are using the script command line driver,
> that means supplying "-solutions 0".
>
> That said, BAB is made for finding one instance of the optimal solution.
> Each new solution returned will be better than the last one returned. Given
> that you let a program run long enough, the last solution is an optimal
> solution to your problem. If you are lucky, or if you branching heuristic is
> very good, you might find the best solution directly, in which case only one
> solution is returned.
>
> If you want all the best solutions, what one should do is first find one
> optimal solution (using BAB as described above). Then one should to a DFS
> search with the problem modified to only accept solutions equivalent to the
> previously found optimal solution.
>
> Cheers,
> Mikael
>
> --
> Mikael Zayenz Lagerkvist, http://www.it.kth.se/~zayenz
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110920/38ff4129/attachment.htm>