Re: [eclipse-clp-users] Query reformulation to achieve better propagation

From: Panagiotis Stamatopoulos <takis_at_...90...>
Date: Tue, 21 Feb 2023 14:01:54 +0200
Dear Marco,

I tried both approaches you suggested. The alldifferent_matrix one
didn't work well. It was very inefficient. Maybe because the grid
representation is a list of lists, which I transformed to a matrix,
in order to post the alldifferent constraint, while the rest of the
program deals with lists? I don't know.

But the second approach, with the lists of the maxima, the ordered
constraint and the gfd nvalues one worked incredibly. It gave a speedup
of almost an order of magnitude (x10) compared to my previous
approach, based on the query of my first message. Thank you very much!

Best Regards,
Panagiotis

On 20-Feb-23 11:40 PM, Marco Gavanelli wrote:
> Dear Panagiotis,
> 
> of course Propia is for rapid prototyping, if you want a fast 
> implementation of the constraint you can implement it with suspensions.
> 
> However, after seeing the whole problem, I think that in order to have a 
> better speedup you should try and use global constraints as much as 
> possible.
> 
> A simple one is alldifferent_matrix.
> 
> Another idea could be the following:
> for each row [X1,X2,...] you have a further list of variables 
> [M1,M2,...] where (foreach i), Mi = max([X1,...,Xi]).
> 
> Now, the list [M1,M2,...] is sorted, so you can impose the ordered 
> constraint on it.
> Also, the number of distinct elements in [M1,M2,...] is exactly the 
> number of skyscrapers you see, so you might use the nvalues constraint 
> (available in gfd).
> 
> I haven't tried these, though.
> 
> Best,
> Marco
> 
> 
> On 20/02/2023 18:28, Panagiotis Stamatopoulos wrote:
>> Thank you very much, Marco. I tried your suggestion and it works
>> as you describe, as far as the constraint propagation is concerned.
>>
>> However, my original problem was to implement an ic-based (or
>> gfd-based) solution for the puzzle here:
>> https://www.puzzle-skyscrapers.com/
>>
>> I got a solution, quite easily, which works well for small and medium
>> size instances, but is very inefficient for larger ones (N > 7). When
>> I injected your propia-based suggestion, the program was even more
>> inefficient. My assumption is - might be wrong, though - that propia
>> introduces an overhead which does not pay off, despite the fact that
>> we have more propagation. I 'll try some more alternatives that I
>> have in mind and see if things get better. As far as the heuristics
>> in the search is concerned, it seems that most_constrained/indomain__max
>> is the best combination for variable/value selection.
>>
>> Anyway, thank you very much again for your time. If there is any
>> suggestion on a way to express more efficiently, compared to the
>> approach that can be inferred from the query in my previouw message,
>> the constraints of the problem above that refer to the numbers of
>> visible skyscrapers from the side points, I would be glad to hear it.
>>
>> Best Regards,
>> Panagiotis
>>
>> On 20-Feb-23 1:54 PM, Marco Gavanelli wrote:
>>> Hi,
>>>
>>> On 20/02/2023 11:27, Panagiotis Stamatopoulos wrote:
>>>> Hello Everybody,
>>>>
>>>> After having loaded libraries ic and ic_global, we give the query:
>>>>
>>>> ?- N = 4, Count = 0, length(L, N), L #:: 1..N, 
>>>> ic_global:alldifferent(L), L = [X1,X2,X3,X4], (X2 #> X1) + (X3 #> 
>>>> max([X1,X2])) + (X4 #> max([X1,X2,X3])) #= Count.
>>>>
>>>> N = 4
>>>> Count = 0
>>>> L = [X1{1 .. 4}, X2{1 .. 4}, X3{1 .. 4}, X4{1 .. 4}]
>>>> X1 = X1{1 .. 4}
>>>> X2 = X2{1 .. 4}
>>>> X3 = X3{1 .. 4}
>>>> X4 = X4{1 .. 4}
>>>> There are 6 delayed goals.
>>>> Yes (0.00s cpu)
>>>>
>>>> As we may see, from the query we can infer that X1 = 4. Is there
>>>> any alternative way to pose the query in order to get this result?
>>>> Note that Count might be anything between 0 and 3 (if we assign it
>>>> the value 3, we get the answer X1 = 1, X2 = 2, X3 = 3, X4 = 4,
>>>> as we might expect). But what if Count is less than 3? How could
>>>> we get the most propagation possible?
>>>
>>> With Count=0 the solver infers that
>>>      (X2 #> X1) #= 0
>>> i.e.
>>>       X2 #=< X1
>>>
>>> I guess you would like to combine that information with the 
>>> alldifferent constraint, and obtain the stronger constraint
>>>
>>>      X2 #< X1.
>>>
>>> One way to achieve this propagation could be to use, instead of the 
>>> #< /3 constraint, a constraint that excludes the possibility of 
>>> having X2 = X1 (i.e., either X1 < X2 or X2 > X1). For example:
>>>
>>> :- lib(propia).
>>> mygt(X,Y,B):- mygt1(X,Y,B) infers most.
>>> mygt1(A,B,1):- A #> B.
>>> mygt1(A,B,0):- A #< B.
>>>
>>> Now this constraint can be used instead of #< /3 :
>>>
>>> ?- N=4, Count=0, L = [X1,X2,X3,X4], length(L, N), L #:: 1..N, 
>>> ic_global:alldifferent(L), mygt(X2,X1,B1), M12 #= max([X1,X2]), 
>>> mygt(X3,M12,B2), M123 #= max([X1,X2,X3]), mygt(X4,M123,B3), 
>>> sumlist([B1,B2,B3]) #= Count.
>>>
>>> N = 4
>>> Count = 0
>>> L = [4, X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}]
>>> X1 = 4
>>> X2 = X2{1 .. 3}
>>> X3 = X3{1 .. 3}
>>> X4 = X4{1 .. 3}
>>> B1 = 0
>>> M12 = 4
>>> B2 = 0
>>> M123 = 4
>>> B3 = 0
>>>
>>>
>>> Delayed goals:
>>>      mygt1(X2{1 .. 3}, 4, 0) infers most
>>>      mygt1(X3{1 .. 3}, 4, 0) infers most
>>>      mygt1(X4{1 .. 3}, 4, 0) infers most
>>>      alldifferent([X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}], 1)
>>> Yes (0.00s cpu)
>>>
>>> Cheers,
>>> Marco
>>>
>>
>>
>> _______________________________________________
>> ECLiPSe-CLP-Users mailing list
>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
> 
Received on Tue Feb 21 2023 - 12:02:16 CET

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET