From: <rui_at_omega.di.uminho.pt>

Date: Mon 05 Feb 2001 01:32:14 PM GMT

Message-ID: <20010205133214.A29578@omega.di.uminho.pt>

Date: Mon 05 Feb 2001 01:32:14 PM GMT

Message-ID: <20010205133214.A29578@omega.di.uminho.pt>

On Sun, Feb 04, 2001 at 06:36:28PM +0000, Joachim Schimpf wrote: > Rui wrote: > > On a special note to the list. I don't know what is the policy about posts > > and so I am not sure if this kind of post fits in. > > Seems to be just the thing to discuss here :-) Good. > > > > Btw, Any comments about my implementation? Is it efficient? > > Can it be improved? > > It is in fact surprisingly tricky to get these things right. > Even this apparently straightforward max-constraint shows many > of the problems that can come up, but that makes it a perfect > example to study! > > > First, your code can be simplified by removing all the special > handling of non-variables. This is possible because most of the > primitives that work on domain variables also work on integers > (considering them as variables with identical upper and lower > bound). This leaves essentially the last clause of your code. > The only place where you still have to check for variables is > where you decide whether to re-suspend or not: I knew that most primitive worked on integers as well. My implementation suffered from the curse of continuous editing. The reason I had sepparated the cases was to simplify the reading (heh) and possible modifications in the special cases. [Code snipped] > > Another important change I have made was to swap the order of > suspend(...) and M::Min..Max. This one baffles me. I had the naive impression from one of the examples on the manual that the other constraints were only ``activated'' when wake was called. > This can be important for correctness when the constraint is > used in a constraint-network together with other constraints > that have higher priority. The line M::Min..Max affects the > domain of M. This may wake other constraints, and if these have > higher priority, they are executed immediately (before M::Min..Max > returns). These other constraints may directly or indirectly > affect the domain of A and B again, which in turn requires maxfd/3 > to be executed again. But that can only work if we have already > suspended it before! Read you loud and clear. > > > The next point is that you don't do all the propagation that is > possible! It is natural to think of the max-constraint as computing > the maximum of two numbers, but in fact a constraint is a relation. > Therefore the "output" argument M can also affect the "input" > arguments A and B. For example You are again right, I didn't look at the constraint as a relation, I guess I was biased by M #= max(A, B). My mistake. [Snip] > > An interesting general point is that we have now split the single > max-constraint into 3 "propagators" which share the job of implementing > the constraint's semantics. This is a typical choice that one has to > make when implementing a constraint: > > - either one propagator that does everything > - or many specialised propagators > > There is no general rule about what is more efficient. It depends on > the particularities of the constraints and also on the actual pattern > of domain updates at runtime. For example, when only lower bound > updates to A happen at runtime, then cheap, specialised propagators > will be more efficient because the irrelevant ones never wake up. > If updates happen randomly to all 6 bounds, then a single propagator > might be more efficient because there is less waking and re-suspending > going on. I guess that in some cases it is hard to know which one would be more appropriate. As usual, a generic implementation is not always the best way to solve all the problems and in some special cases, implementing a specific one for the problem at hand might be the best. > > I have now used the lower-level primitives dvar_remove_smaller > and dvar_remove_greater instead of ::/2 and #=</2. > This is somewhat more efficient, but otherwise equivalent. Yup, as I guess that ::/2 and #=</2 may call those lower-level primitives themselves. > > Also, I have wrapped all the updates of M, A and B together with > the re-suspend code into a call_priority/2. This makes the whole > sequence sufficiently "atomic", i.e. any waking of other constraints > will be postponed until the end of the call_priority. This is an > alternative way to achieve what we did before by playing with the > order of modification and re-suspension. Interesting, took a note of that as well. [Snip again] > > After all this, is it worth remembering that the most "complete" > implementation of a constraint is not necessarily the best under all > circumstances. In our example, the perfect constraint has to wake up > on all 6 possible changes (upper/lower bound change on 3 variables). > Every change may or may not represent a propagation opportunity. If > it doesn't, we have just wasted time, and we would possibly have been > better off using a cheaper, incomplete implementation. By the way, > this is one reason why most so-called "benchmarks" of constraint > systems are quite useless. That is one aspect I already had in mind. That the most "complete" implementation of a constraint is not necessarily the best. Well, that is one reason why constraints like A*B #= 10 do not prune all the spurious values from A and B and leave only the ones that can possibly work. > > > There are more interesting aspects, but I leave then for later... > Just want to mention that the library(fd_global) contains a > generalisation of the max-constraint called maxlist/2, which computes > the maximum of a list, but also works efficiently for 2 variables. Well, thank you Joachim for taking your time to explain some of the important notions behind propagation and Eclipse. I learned a few things with your modifications of my code. > Joachim Schimpf / phone: +44 20 7594 8187 > IC-Parc, Imperial College / mailto:J.Schimpf@ic.ac.uk > London SW7 2AZ, UK / http://www.icparc.ic.ac.uk/eclipse > --Rui MendesReceived on Mon Feb 05 12:30:00 2001

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:07 PM GMT GMT
*