Actually, there is the smartest possible propagator: it inself uses search do determine the acurate solution set.
Christian -----Original Message----- From: Russ Abbott [mailto:[EMAIL PROTECTED] Sent: Wednesday, October 26, 2005 10:25 PM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Implementing constraints If, as I think we all agree, the leverage in constraint programming comes from reasoning about domains, a good argument for doing that in a language like Oz is that Oz is a more powerful language for reasoning about anything than is C++ (or Java for that matter). What I'm thinking about is this. Propagators reason about and draw conclusions about domains. If one has particular conclusions one wants to draw and one knows how to draw them (e.g., if X >: Y then Y's domain must be restricted to values greater than X), then it's fine to draw those conclusions in C++. But I can imagine a situation in which one wants to write a propagator that itself has to do some fancy reasoning. (I'm not expert enough in this field to come up with an example.) In cases like that (and I would bet that there will be some), then the leverage one gets from using a language like Oz for writing the propagator will probably be worth the price. This will be especially relevant since propagators are the engine of speedup. If propagators themselves can be smart, then the speedup can be even more significant. The smarter the propagator; the more limited the need for search. There is probably a theorem here about how much search it is worth putting into a propagator before it becomes self-defeating. If the propagators do enough work, perhaps the result is a theorem proving system in which all the search is in the propagators or about the constraints and domains and no search for elements within the domains is necessary. (Has someone already worked this out?) -- Russ On 10/26/05, Russ Abbott <[EMAIL PROTECTED]> wrote: Hi Christian, I'm so happy to get your comments. But ... (see below). On 10/26/05, Christian Schulte < [EMAIL PROTECTED] > wrote: Dear all, I have been following this discussion with quite some interest, however I was unably to throw in something. Here it comes. The first point I would like to re-iterate on (Grégoire and Raphaël already went there) is the tremedous difference between the essence of constraint programming and generate and test. The very idea of constraint programming is to open up variables so that they can specify what are values which still can participate in a solution. By this, one describes (partially) a set of solutions to the problem. With generate and test, one only describes a single partial assignment. Why this matters: the inference you can do in principle for generate and test is to find out that the current partial assignment can not be extended to a solution. And if one finds out the only thing is to backtrack! Now for constraint programming, inference (constraint propagation, that is) can remove some assignments (as described by the projections onto the involved variables) without being forced to backtrack. The difference is typically at least exponential. I don't see how you get any kind of improvement if the domains are simple sets of values with no structured relationships among the elements, i.e., no 'less-than' or other relationships other than equality. (One might get a constant speed-up in that it may be faster to remove an element from a domain than to generate a computation that uses that element and then kill it immediately.) The other point I'd like to make is to discourage Russ to implement propagators in Oz. Yes, one can do it. And yes, one can dig a hole with a spoon. However, pick your tool well! Evidence has it that you are way better of to implement a constraint as a propagator in C++ than in Oz. This is partially due to efficiency concerns (these guys need to be really really fast). But alos, as it comes to numerical and graph algorithms, C++ is just the better pick. Of course, I am somehow biased as I abandoned Oz in favour of my new pet: Gecode, a constraint programming environment entirely developed in C++ (check www.gecode.org, we are going to release on Nov 24th). I understand the desire for speed. But my preference is for beauty first. I'll admit that I don't solve real problems; I just like to think about elegant mechanisms that let other people solve them. If Gecode is as it appears to be a C++ library, I regret to say that I probably won't spend the time to find out about it. There are lots of powerful libraries out there that I don't know about. I'll admit as well to another prejudice. I don't like C++. I much prefer Java. I know that at least half the programming world disagrees with me (and I don't want to start a C++ vs. Java discussion here), but probably at least 99% of the programming world has never even heard of either logic programming or constraint programming. What attracted me to Oz in the first place and what has kept me interested in it is the possibility of exploring programming language paradigms in an integrated framework. I know that this is not the same thing as wanting a light-speed constraint solver. I guess we each have our own priorities--and mine are not necessarily universally shared :-( -- Russ -- _____________________________________________ Professor, Computer Science California State University, Los Angeles o Check out my blog at http://russabbott.blogspot.com/ _________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
