Re: [eclipse-clp-users] How can bb_min fail after finding a solution?

On 15/02/2013 16:29, Matthew Skala wrote:
> I'm getting output like this from bb_min/3:
>
>     Found a solution with cost 6
>     Found a solution with cost 5
>     Found a solution with cost 4
>     Found no solution with cost 0.0 .. 3.0
>
>     No (0.06s cpu)
>
> How can this be?  If the labelling routine ever succeeds, then shouldn't
> bb_min also succeed?
>
> My labelling routine is a complicated one involving Cardinal and a bunch
> of hand-implemented heuristics.  I'm trying now to come up with a minimal
> example to demonstrate the above behaviour; but if there exists a simple
> and general explanation of the circumstances under which bb_min is able to
> return failure after labelling has succeeded, that would help.  I suspect
> that Cardinal may be misbehaving in some way, along the lines of leaving
> suspended goals; but I don't think suspended goals are exactly the problem
> because I have also seen bb_min succeed with labelling routines that left
> suspended goals.

During search, bb_min always saves the "best solution so far".  Once search
is finished, the last saved solution is the optimum.  bb_min then instantiates
the problem variables to this solution, and this will wake up the constraints
one more time - which should of course succeed.  If it doesn't succeed, then
either, as you suspect, the solution found during search wasn't really a
solution (e.g. because there were unsolved constraints) and/or there is
a bug in a constraint implementation (making it behave differently
depending on how it is woken).

To avoid this last step, you can use bb_min/6
http://eclipseclp.org/docs/current/bips/lib/branch_and_bound/bb_min-6.html
which simply returns the optimum cost and solution values in arguments.
You can the unify them manually (possibly one-by-one in a loop) and
see why it fails.

To check whether delayed goals are left at the end of search, check by
calling delayed_goals/1 after your labeling succeeds.


>
> Trying to step through it in the debugger doesn't seem to work - after it
> has found a solution, the "step" command in the debugger never returns to
> a prompt.  I don't know if it is merely slowed down by a factor of many
> thousands, or not debuggable at all, or if "step" is the wrong way to do
> it, but in any case I haven't been able to get a debugging session to the
> point where bb_min is failing.

This is indeed a known problem (sorry we should at least document this
as long as it is not fixed - it's tricky) related to the implementation
of bb_min's continue-strategy.  Try the 'restart' strategy, which doesn't
have this problem.


>
> I might be able to work around the issue by making my labelling routine
> save the best solution it finds - then I could ignore bb_min's success or
> failure - but in that case, I'll be close to having reimplemented bb_min
> for myself.

That's right, but using bb_min/6 should make that unnecessary.


Hope that helps,
-- Joachim