Hi, here are my timings for the complete set of options for Select and Choice in ic:search/6, using Hakan's constraint model: indomain / input_order / 9.11 indomain / first_fail / 3.24 indomain / anti_first_fail / 9.23 indomain / smallest / 9.01 indomain / largest / 8.57 indomain / occurrence / 0.58 indomain / most_constrained / 1.20 indomain / max_regret / 9.05 indomain_min / input_order / 4.19 indomain_min / first_fail / 1.45 indomain_min / anti_first_fail / 4.08 indomain_min / smallest / 4.10 indomain_min / largest / 3.65 indomain_min / occurrence / 0.26 indomain_min / most_constrained / 0.76 indomain_min / max_regret / 4.18 indomain_max / input_order / 0.44 indomain_max / first_fail / 0.23 indomain_max / anti_first_fail / 0.37 indomain_max / smallest / 0.45 indomain_max / largest / 0.32 indomain_max / occurrence / 1.11 indomain_max / most_constrained / 1.84 indomain_max / max_regret / 0.44 indomain_middle / input_order / 0.50 indomain_middle / first_fail / 0.28 indomain_middle / anti_first_fail / 0.43 indomain_middle / smallest / 0.51 indomain_middle / largest / 0.37 indomain_middle / occurrence / 1.52 indomain_middle / most_constrained / 2.94 indomain_middle / max_regret / 0.54 indomain_reverse_min / input_order / 0.28 indomain_reverse_min / first_fail / 0.16 indomain_reverse_min / anti_first_fail / 0.24 indomain_reverse_min / smallest / 0.30 indomain_reverse_min / largest / 0.20 indomain_reverse_min / occurrence / 0.58 indomain_reverse_min / most_constrained / 1.93 indomain_reverse_min / max_regret / 0.28 indomain_reverse_max / input_order / 3.83 indomain_reverse_max / first_fail / 1.70 indomain_reverse_max / anti_first_fail / 3.66 indomain_reverse_max / smallest / 3.64 indomain_reverse_max / largest / 3.15 indomain_reverse_max / occurrence / 0.38 indomain_reverse_max / most_constrained / 0.50 indomain_reverse_max / max_regret / 3.62 indomain_median / input_order / 0.50 indomain_median / first_fail / 0.28 indomain_median / anti_first_fail / 0.42 indomain_median / smallest / 0.51 indomain_median / largest / 0.36 indomain_median / occurrence / 1.51 indomain_median / most_constrained / 3.12 indomain_median / max_regret / 0.50 indomain_split / input_order / 0.53 indomain_split / first_fail / 0.28 indomain_split / anti_first_fail / 0.53 indomain_split / smallest / 0.53 indomain_split / largest / 0.43 indomain_split / occurrence / 0.09 indomain_split / most_constrained / 0.13 indomain_split / max_regret / 0.53 indomain_reverse_split / input_order / 0.06 indomain_reverse_split / first_fail / 0.04 indomain_reverse_split / anti_first_fail / 0.06 indomain_reverse_split / smallest / 0.06 indomain_reverse_split / largest / 0.06 indomain_reverse_split / occurrence / 0.34 indomain_reverse_split / most_constrained / 0.52 indomain_reverse_split / max_regret / 0.07 indomain_random / input_order / 6.34 indomain_random / first_fail / 3.67 indomain_random / anti_first_fail / 7.43 indomain_random / smallest / 11.30 indomain_random / largest / 5.41 indomain_random / occurrence / 2.26 indomain_random / most_constrained / 3.65 indomain_random / max_regret / 3.16 indomain_interval / input_order / 0.79 indomain_interval / first_fail / 0.42 indomain_interval / anti_first_fail / 0.80 indomain_interval / smallest / 0.79 indomain_interval / largest / 0.63 indomain_interval / occurrence / 0.14 indomain_interval / most_constrained / 0.25 indomain_interval / max_regret / 1.06 indomain_reverse_split is clearly the fastest choice option for this particular problem, especially together with first_fail as selection option. Interestingly, depending on the choice option, occurrence and most_constrained as selection schemes work either much better or much worse than the rest. Cheers, Thorsten Am 13.09.2011 08:42, schrieb Thorsten Winterer: > 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-usersReceived on Tue Sep 13 2011 - 09:46:47 CEST
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET