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

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

-- 
Marco Gavanelli
Coordinator of the courses
-L8 Electronics and Computer Science Engineering
-LM29 Electronics Engineering for ICT
-LM32 Computer Science and Automation Engineering
Associate Professor
Ph.D. in Computer Science Engineering
Dept of Engineering
University of Ferrara
Tel/Fax  +39-0532-97-4833
http://docente.unife.it/marco.gavanelli