Hi, using ordered_sum/2 is an excellent idea. It improves the runtime a lot. According to my experiments, the best selection option for search/6 is now 'largest', especially if you also consider the time needed to prove the uniqueness of the solution. As for the choice option, 'indomain_reverse_split' seems to be still the quickest. (sometimes it's a good thing not to have the fastest machine... :-) ) Cheers, Thorsten Am 13.09.2011 11:15, schrieb Marco Gavanelli: > Hi all, > > well, now there is no need to improve further, however another lesson in > CP is try to use the available global constraints. ECLiPSe has the > interesting ordered_sum constraint, so one can join the symmetry > breaking with the sum constraint. > > I checked this model with the old labeling (as with the smart search > suggested by Thorsten I could not even measure the computing time), and > it went from 9.22 seconds to 2.78 on my machine. > > Cheers, > Marco > > On 13/09/11 08:42, Thorsten Winterer wrote: >> Hi, >> >> just for completeness I would use #=</2 instead of #</2 for the symmetry >> breaking (although #</2 of course gives the same solution). >> >> But for search/6, I think there are better choices than 'largest' and >> 'indomain_split' available. >> >> With 'largest' and 'indomain_split', I need 0.52 sec to find the >> solution on my machine instead of 67.81 sec. >> >> With 'first_fail' and 'indomain_reverse_split', I need only 0.04 sec. >> >> >> Cheers, >> Thorsten >> >> >> Am 13.09.2011 06:56, schrieb Hakan Kjellerstrand: >>> Hi, >>> >>> another improvement is adding explicit symmetry breaking: >>> >>> A #< B, >>> B #< C, >>> C #< D, >>> >>> as well as using another labeling >>> >>> search(Prices ,0,largest,indomain_split,complete,[]), >>> >>> This solves the problem in 0.22 seconds instead of the original >>> about 45 seconds on my machine. >>> >>> In larger problems I would probably also have used the >>> explicit domain declaration >>> >>> Prices :: [1..711] >>> >>> though in this case it doesn't improve times or the number of >>> backtracks. >>> >>> Here's the full model: >>> >>> %%%%%%%% >>> :- lib(ic). >>> >>> solve :- >>> Sum = 711, >>> Product = 711, >>> Prices = [A, B, C, D], >>> % A #> 0, B #> 0, C #> 0, D #> 0, >>> Prices :: [1..711], >>> A + B + C + D #= Sum, >>> A * B * C * D #= Product * 1000000, >>> >>> A #< B, >>> B #< C, >>> C #< D, >>> search(Prices ,0,largest,indomain_split,complete,[backtrack(Backtracks)]), >>> >>> % labeling(Prices), >>> >>> writeln(Prices), >>> writeln(backtracks:Backtracks). >>> >>> %%%%%%%%% >>> >>> >>> Best, >>> >>> Hakan >>> >>> >>> On Tue, Sep 13, 2011 at 02:00:28AM +0200, Joachim Schimpf wrote: >>>> Sergey Dymchenko wrote: >>>>> Hi! >>>>> >>>>> I'm trying to solve this puzzle: http://programmingpraxis.com/2009/11/27/7-11/ >>>>> >>>>> Here is my very straightforward code: >>>>> >>>>> :- lib(ic). >>>>> solve :- >>>>> Sum = 711, >>>>> Product = 711, >>>>> Prices = [A, B, C, D], >>>>> A #> 0, B #> 0, C #> 0, D #> 0, >>>>> A + B + C + D #= Sum, >>>>> A * B * C * D #= Product * 1000000, >>>>> labeling(Prices), >>>>> writeln(Prices). >>>>> >>>>> It works, but it's too slow. >>>>> Is there any way to speed it up without being too clever and >>>>> explicitly say to ECLiPSe that the prices of the four items must come >>>>> from the list of divisors of 711? >>>> It is much faster (1.8 instead of 63 seconds on my machine) if you use >>>> domain splitting during search, i.e. replace labeling(Prices) with >>>> >>>> search(Prices, 0, input_order, indomain_split, complete, []) >>>> >>>> This is probably always a good idea with relatively large domains >>>> and convex constraints. >>>> >>>> Other improvements? >>>> >>>> >>>> Cheers, >>>> Joachim >>>> >>>> ------------------------------------------------------------------------------ >>>> BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA >>>> Learn about the latest advances in developing for the >>>> BlackBerry® mobile platform with sessions, labs& more. >>>> See new tools and technologies. Register for BlackBerry® DevCon today! >>>> http://p.sf.net/sfu/rim-devcon-copy1 >>>> _______________________________________________ >>>> ECLiPSe-CLP-Users mailing list >>>> ECLiPSe-CLP-Users_at_lists.sourceforge.net >>>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >> >> ------------------------------------------------------------------------------ >> BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA >> Learn about the latest advances in developing for the >> BlackBerry® mobile platform with sessions, labs& more. >> See new tools and technologies. Register for BlackBerry® DevCon today! >> http://p.sf.net/sfu/rim-devcon-copy1 >> _______________________________________________ >> ECLiPSe-CLP-Users mailing list >> ECLiPSe-CLP-Users_at_lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >> >> >Received on Tue Sep 13 2011 - 11:26:29 CEST
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST