Re: Q: minimize

From: Warwick Harvey <wh_at_icparc.ic.ac.uk>
Date: Fri 09 Aug 2002 04:26:38 PM GMT
Message-ID: <20020809172637.P22613@tempest.icparc.ic.ac.uk>
On Fri, Aug 09, 2002 at 10:17:05AM +0100, Marc van Dongen wrote:
> Hi again,
> 
> 
> I've one more question regarding minimize.
> 
> I'm using it as follows:
> 
>  VS :: 0..1,
>  constrain variables in VS,
>  EXPR :: 960..1024,
>  EXPR #= LENGTHS * VS,
>  minimize( labeling( VS ), EXPR ).
> 
> minimize now outputs:
> 
> Found a solution with cost 960
> 
> and does not immediately terminate (I've given it 20 seconds
> and then interrupted the computation).
> 
> If I replace minimize by min_max then min_max *does* immediately
> terminate after having output
> 
> Found a solution with cost 960
> 
> Am I missing something?

Apparently FD's minimize/2 can be a bit late in imposing the new cost
bound.  The general problem here is that if you impose a new bound after
finding a solution, backtracking occurs, immediately retracting the new
bound.  What one really wants is a way to have the bound re-imposed after
any failure, simulating it being applied in a more global context.
Facilities for doing this were not available in ECLiPSe until quite
recently, so back when this library was written other (not as good)
techniques had to be used instead.

Anyway, I suggest you try using the branch_and_bound library.  The
minimize/2 there seems to do it right (using the new facilities), and I'm
led to believe that's the preferred library to use for this stuff.  Probably
FD's routines were not updated when the new techniques became available
since we are planning to phase that library out.

Cheers,
Warwick
Received on Fri Aug 09 17:27:08 2002

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:16 PM GMT GMT