Re: [eclipse-clp-users] 7.11 puzzle

From: Thorsten Winterer <thorsten_winterer_at_web.de>
Date: Tue, 13 Sep 2011 11:46:25 +0200
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&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
>>> Learn about the latest advances in developing for the
>>> BlackBerry&reg; mobile platform with sessions, labs&   more.
>>> See new tools and technologies. Register for BlackBerry&reg; 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&reg; DevCon Americas, Oct. 18-20, San Francisco, CA
> Learn about the latest advances in developing for the
> BlackBerry&reg; mobile platform with sessions, labs&  more.
> See new tools and technologies. Register for BlackBerry&reg; 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 - 09:46:47 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET