Re: [eclipse-clp-users] 7.11 puzzle

From: Thorsten Winterer <thorsten_winterer_at_web.de>
Date: Tue, 13 Sep 2011 13:26:01 +0200
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&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 - 11:26:29 CEST

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