Re: [eclipse-clp-users] On stating a strange constraint

From: Panagiotis Stamatopoulos <takis_at_...90...>
Date: Mon, 27 Mar 2023 13:27:53 +0300
Yes, it worked!!! Marco, thank you very much, indeed!

And, Hakan, thank you very much for the info on the value_precede_chain
global constraint. It is exactly what I was looking for, but in an
ECLiPSe environment. Marco's suggestion is actually a simple and
correct implementation of it.

Best Regards,
Panagiotis

On 27-Mar-23 12:58 PM, Panagiotis Stamatopoulos wrote:
> Hi Marco,
> 
> Yes, you are right. The ultimate purpose of this constraint is
> symmetry breaking. I 'll try what you suggest. Thanks!
> 
> Regards,
> Panagiotis
> 
> On 27-Mar-23 12:51 PM, Marco Gavanelli wrote:
>> Hi Panagiotis,
>>
>> this constraint reminds me of a symmetry breaking labeling proposed by 
>> Pedro Meseguer.
>>
>> Anyway, what about:
>>
>> L[0] = 1
>>
>> forall i>0
>>      L[i] <= maxlist(L[0..(i-1)]) + 1
>> ?
>>
>> I hope the intuition is clear, with L[0..(1-i)] I mean the sublist of 
>> the first i elements of the list L.
>>
>> Best,
>> Marco
>>
>>
>> On 27/03/2023 11:34, Panagiotis Stamatopoulos wrote:
>>> Hello Everybody,
>>>
>>> I am seeking ideas on how to implement in ECLiPSe a specific
>>> constraint in a simple, if possible, and efficient way.
>>>
>>> Let L be a list of length N with domain variables ranging
>>> in 1..M. Acceptable lists are the ones that ...
>>> 1. ... contain values from 1 up to K (K =< M), but not any
>>> values from K+1 up to M (K is not given).
>>> 2. ... satisfy the condition that the first occurrences of
>>> the values from 1 to K appear in this order in the list.
>>>
>>> For example, let N = 8 and M = 5. The lists [1,1,2,1,2,3,2,1]
>>> and [1,2,1,3,2,4,3,1] are valid. The first one has K = 3 (only
>>> items 1, 2, 3 appear in the list) and the second one has K = 4
>>> (just 5 is missing from the list). In the first list, the first
>>> occurrences of 1, 2, 3 are in positions 1, 3, 6 and in the second
>>> list, the first occurrences of 1, 2, 3, 4 are in positions 1, 2,
>>> 4, 6 in the lists. All fine!
>>>
>>> I believe that the requirement 1 above could be implemented
>>> easily with the occurrences constraint (one for each number in
>>> 1..M) and a set of implication (=>) constraints, stating that
>>> if the number of occurrences of x in 1..M is 0, then the numbers
>>> of occurrences of x+1, x+2, ... in the list should also be 0.
>>> I cannot predict the propagation level of this approach, but
>>> it seems that, at least, declaratively can be stated.
>>>
>>> I don't have any good ideas for the requirement 2. I tried
>>> something that exploits again the occurrences constraint (for
>>> every number in 1..M and every prefix list of the given list)
>>> and then the lex_le constraint. It worked, but if N is around
>>> 50 or more, the efficiency is unacceptable.
>>>
>>> Any ideas on the above would be more than welcome.
>>>
>>> Best Regards,
>>> Panagiotis
>>>
>>>
>>> _______________________________________________
>>> ECLiPSe-CLP-Users mailing list
>>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>>
> 
> 
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
Received on Mon Mar 27 2023 - 10:27:56 CEST

This archive was generated by hypermail 2.3.0 : Wed Sep 25 2024 - 15:13:21 CEST