[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

efficient minlist constraint using FD files

From: Hector Palacios
Subject: efficient minlist constraint using FD files
Date: Tue, 26 Mar 2002 16:34:19 -0400 (VET)

I'm trying to get better my implementation
of fd_minlist(Min, List) constraint.

It means that min(Min) == min({ min(Li) / Li \in L })
          and max(Min) == min({ max(Li) / Li \in L })

Actualy I have a version working:
fd_minlist(fdv M, l_fdv L)
  start M in Fd_Min_FromList(L) trigger on dom (L) 
  start forall Li of L do Li in min(M) .. max_integer

where Fd_Min_List calc the range mins over L.

But performance is very important to me, and the
problem is that every time some variable on L
is touched, minlist is recalculated. O(n) operations.

I would like to check first if the variable
that was touched, will be change the range of Min.

So, Im trying something like that.
fd_minlist2(fdv M, l_fdv L)
  start forall Li in L do 
           exit if (min (Li) > min (M) && max (Li) > max(M)) 
           M in Fd_Min_FromList(L) trigger on dom(Li)

        (* like the previuos one *)
  start forall Li of L do Li in min(M) .. max_integer

It try to work over items on L, exit
without recalculate if (min (Li) > min (M) && max (Li) > max(M)) 
because it does not matters.
Or recalculate using my old function.

But it have some problems...
1. I think that within a forall Li in L 
we can't use L variable.
2. The guard "exit if" only can be used 
before the forall, where i dont have access
to Li items. I saw that at FD_SYNTAX file.

May be that using c functions in one places
named at FD_SYNTAX, it could work.
But I dont understand that...
Any idea??

It is very important. 
We have a deadline to a conference very close.

Thanks in advance for your help and
for gprolog...

Hector L. Palacios V. - Dpto. Computacion y TI
       Grupo de Inteligencia Artificial 
+58-212-9063257(Ofic)     +58-212-9063243(Fax)
   Ama y haz lo que quieras.    San Agustin.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]