Re: [eclipse-clp-users] Instantiation fault in bb_min with non-default strategy

From: Sergii Dymchenko <kit1980_at_gmail.com>
Date: Fri, 13 Mar 2015 15:00:02 -0700
Joachim,

Thank you. This way the dichotomic strategy works. But for the problem the
running time is much larger than with continue strategy, contrary to what I
expected...

And why continue strategy works without manually instantiating Cost? Pure
luck?

-Sergii.




On Fri, Mar 13, 2015 at 2:37 PM, Joachim Schimpf <jschimpf_at_coninfer.com>
wrote:

> On 13/03/15 19:39, Sergii Dymchenko wrote:
> > Hi,
> > I wrote a blog post about solving PuzzlOR "Electrifying" puzzle with
> ECLiPSe:
> > http://sdymchenko.com/blog/2015/03/13/electrifying-eclipse/
> >
> > While solving the puzzle I encountered and issue with bb_min and
> strategies
> > other than the default one.
> >
> > Consider this program (basically the same program as in the blog post
> linked):
> >
> > :- lib(ic).
> > :- lib(branch_and_bound).
> > solve(HouseXs, HouseYs, K, GenXs, GenYs, Cost) :-
> >      dim(HouseXs, [N]),
> >      MaxX #= max(HouseXs), MaxY #= max(HouseYs),
> >      dim(GenXs, [K]), dim(GenYs, [K]),
> >      GenXs :: 1..MaxX, GenYs :: 1..MaxY,
> >      ( for(I, 1, N), foreach(Di, Distances), param(HouseXs, HouseYs,
> GenXs, > GenYs, K) do
> >          ( for(J, 1, K), fromto(1.0Inf, Dprev, Dcurr, Di), param(I,
> HouseXs, > HouseYs, GenXs, GenYs) do
> >              Dcurr $= min(Dprev, sqrt(sqr(HouseXs[I] - GenXs[J]) + >
> sqr(HouseYs[I] - GenYs[J])))
> >          )
> >      ),
> >      Cost $= sum(Distances),
> >      bb_min(search([](GenXs, GenYs), 0, most_constrained,
> indomain_middle, > complete, []), Cost, bb_options{delta:0.1,
> strategy:dichotomic}).
> >
> > main :-
> >      HouseXs = [](2, 2, 3, 3, 4, 4,  5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 8, 9,
> 9, 10),
> >      HouseYs = [](2, 5, 6, 8, 2, 10, 2, 3, 6, 8, 1, 5, 2, 8, 5, 7, 8, 4,
> 7, 3),
> >      solve(HouseXs, HouseYs, 3, GenXs, GenYs, _Cost),
> >      ( foreacharg(X, GenXs), foreacharg(Y, GenYs) do
> >          LetterCode is 0'A + Y - 1,
> >          char_code(Letter, LetterCode),
> >          write(X), write(Letter), nl
> >      ).
> >
> > With strategy:dichotomicI get:
> >
> > Found a solution with cost 67.5083636407248__67.50836364072498
> > Found no solution with cost 0.0 .. 33.75418182036249
> > instantiation fault in 33.75418182036249 =< _325826{49.307233137943534 ..
> > 49.30723313794369}
> > abort
> >
> > There is a similar issue with strategy:restart, but the program works OK
> with
> > the default continuestrategy.
> > Is this an ECLiPSe bug?
>
>
> Not strictly a bug, but an unhelpful error message.  bb_min expects the
> search
> routine to instantiate the Cost variable, which, as often with continuous
> variables, isn't the case here.
>
> What you have to do is instantiate the Cost variable to a bounded-real
> constant,
> after the search has finished, like so:
>
>       bb_min((
>                search(...),
>                get_var_bounds(Cost,CostL,CostH),
>                breal_from_bounds(CostL,CostH,Cost)
>            ),
>            Cost,
>            bb_options{delta:0.1, strategy:dichotomic} )
>
>
>
> -- Joachim
>
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming The Go Parallel Website,
> sponsored
> by Intel and developed in partnership with Slashdot Media, is your hub for
> all
> things parallel software development, from weekly thought leadership blogs
> to
> news, videos, case studies, tutorials and more. Take a look and join the
> conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
Received on Fri Mar 13 2015 - 22:00:09 CET

This archive was generated by hypermail 2.2.0 : Sun Apr 05 2015 - 21:13:22 CEST