|
From: Laurent C. <cai...@de...> - 2002-08-14 08:08:07
|
Hello,
> My current problem is lack of knowledge regarding
> constraint programming in general.
WASA is a project ordered by Philippe Codognet, a CSP expert, to
"new to constraints" students who were given a 2-month work of
making a framework for implementing the ASA. Florent Selva has a
strong mathematical backround, and Laurent Caillette has
a strong experience in software design, so WASA is a way
to make CSP when you know nothing about it (this is also
true for its designers and implementors !).
> The one I currently use in JCL is a forward checking
> algorthm with full arc consistency checking and dynamic
> variable ordering. However I'm not completely happy with
> it's implementation so I'd be forced to re-implement it.
> (...)
> And I preferable want to be able to model my problems
> using business domain objects (like Activity, Resource,
> etc), and relation in business domain relations
> (Activity.startAfterEnd(activity)).
OK, everything's clear now :
- conventional solvers give good results for your
problem,
- but they lead to poor design, and you want to
avoid that mess.
The bad news is, there is no other solution than writing
your system twice : one time with good objects, one time
with good variables and constraints.
You can attempt to perform a mix by customzing a solver,
but we've no idea of the problems you will encounter.
We just believe that it'll give you hard times.
Why does it seem impossible to write good things like :
Activity.startAfterEnd(activity) ? Look at the rules
a solver manipulates. If I write :
equals( sum(A, B), 3)
the solver can build a graph of dependancies between
A and B, the sum(), and other things happening elsewhere.
Then, it can determine which nodes to prune during
evaluation. Plain ol' Java allows things like :
int b2 = b ;
a2 = a ;
a += b2 ;
if( a == 3 ) { good }
a = a2 ;
The solver cannot find rules out of that mess. If you
try to do the same with methods, you've to save the
whole application context before evaluating a constraint.
This save can be *very costy*, depending of your
application.
> It looks like you have the same intention even though
> you are tying it to ASA (which I can't really figure
> out why). I'm not convinced that "completly different
> of what conventional solvers offer" is 100% accurate.
We provide context saving on objects (say bye to the
perfs), and allow to write Constraints with any messy
Java code, because the WASA solver doesn't attempt to
understand them : it just applies, and look at the
variable's errors. The Constraints just have to set
error scores, there is nothing like forward checking
or whatever.
> ASA however looks like a fairly simple algorithm (at
> least to understand), is this observation correct or
> simply an illusion based on good explanation in the
> paper?
The paper describes a generalistic approach, but does
not explain everything you should know about Tabu List
management or things like that. We had some hard times
for understanding what was *really* happening in the
system (though coding may appear simple).
BTW we're interested by your feedback about JCL. We
believe that CSP is a *great* tool, and we want to
keep an eye on what's happening here.
Regards.
The WASA Team
> Howdy,
>
> sending this to the users list now.
>
> Yes, two weeks (or 2-4) is really not much time, but it's all I got for
> the moment. I'm a farily good coder so the programming isn't the
> problem. I think I would be able to wrap something up in a week since I
> allready have the solver algorithms in place, the design is the nut to
> crack. My current problem is lack of knowledge regarding constraint
> programming in general. Last week I must have read pretty much every
> web-site that exists on the topic (at least it feels like it) and I
> still struggle with understanding some concepts in this paradigm. The
> vocabulary in use isn't exactly stream-lined with respect to users like
> me (fairly good programmer, suck at anything even remotly related to
> math). But to be honest, most of this feels like common sense, and most
> of the algorithms aren't that hard to grasp, at least as long as you
> don't have to invent them :-)
>
> Thus I can't really fully answer your question regarding ILOG's
> algorithms. But I can pretty much assure you that ILOG doesn't use
> simple backtracking for their solvers. They do provide different search
> schemes that one can use so it's hard to say exactly which one they use
> for scheduling (or as they say, "you have to experiment with this since
> their doesn't exists a determenistic way of choosing beforehand").
> The one I currently use in JCL is a forward checking algorthm with full
> arc consistency checking and dynamic variable ordering. However I'm not
> completely happy with it's implementation so I'd be forced to
> re-implement it. I'm not sure if this uses some sort of tabu search
> (have to look closer at it) which would make it look pretty close to ASA
> I guess. ASA however looks like a fairly simple algorithm (at least to
> understand), is this observation correct or simply an illusion based on
> good explanation in the paper?
>
> But this is mearly a matter of style in the end. I want a CP package
> that clearly separate solving from modelling. And I preferable want to
> be able to model my problems using business domain objects (like
> Activity, Resource, etc), and relation in business domain relations
> (Activity.startAfterEnd(activity)). It looks like you have the same
> intention even though you are tying it to ASA (which I can't really
> figure out why). I'm not convinced that "completly different of what
> conventional solvers offer" is 100% accurate. ILOG provides this with
> business domain specific modelling API's (Scheduler, Dispatcher, Rules,
> etc).
>
> Anyway, I'll have a look at it, try to get it running, and see what
> happens :-)
>
> Cheers,
> /Niclas
|