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

Hi Panaglotis,

>there are cases where a lif(gfd) based CP program is quite
>slower than the equivalent one based on the native ECLiPSe constraint
>libraries.

Do you see any pattern to what problems are slower in lib(gfd)? I
would like to study such programs to see if this is a property of
Gecode, or the gfd implementation.

I expect that most global constraints will be faster in Gecode, not
only because they are implemented at a C/C++ level, but also because
many of them are probably based on better algorithms. Additionally,
Gecode provides more global constraints than the native solvers.

When you use lib(gfd), do you do the search in ECLiPSe, or in Gecode?
To do the search in Gecode, you need to use gfd:search/5:

http://eclipseclp.org/doc/bips/lib/gfd/search-6.html

I expect doing search in Gecode is faster, because you do not keep
switching between ECLiPSe and Gecode, but is less flexible. I would be
interested if you have found cases where doing the search in EC:iPSe
is faster.

We have not had much feedback on lib(gfd), and welcome any feedback on
it (and of course for any other parts of ECLiPSe) from our users.

Cheers,

Kish

On Mon, Mar 27, 2023 at 5:25 PM Panagiotis Stamatopoulos
<takis_at_...90...> wrote:
>
> Yes, Kish. What I need is also done by precede/2 with lib(gfd).
>
> However, what I have noticed is that although in many cases lib(gfd)
> is faster than lib(ic)/lib(ic_global), which someone would expect to
> be the case, as a compiled C++ code should run faster than a Prolog
> program, there are cases where a lif(gfd) based CP program is quite
> slower than the equivalent one based on the native ECLiPSe constraint
> libraries.
>
> Best Rehards,
> Panagiotis
>
> On 27-Mar-23 4:57 PM, Kish Shen wrote:
> >> And, Hakan, thank you very much for the info on the value_precede_chain
> >
> > This constraint is implemented in Gecode, and is available for ECLiPSe
> > through lib(gfd) as precede/2:
> >
> > http://eclipseclp.org/doc/bips/lib/gfd/precede-2.html
> >
> > Most of Gecode's constraints are available to ECLiiPSe through
> > lib(gdfd). You can check on which constraints are in the various
> > ECLiPSe finite domain libraries at:
> >
> > http://eclipseclp.org/doc/bips/finite-domain_constraints.html
> >
> > Cheers,
> >
> > Kish
> >
> >
> > On Mon, Mar 27, 2023 at 11:28 AM Panagiotis Stamatopoulos
> > <takis_at_...90...> wrote:
> >>
> >> 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
> >>
> >>
> >> _______________________________________________
> >> 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
>
>
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users