[Wasa-users] Re: WASA

[Niclas O. <gu...@ac...>]

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=20
the moment. I'm a farily good coder so the programming isn't the=20
problem. I think I would be able to wrap something up in a week since I=20
allready have the solver algorithms in place, the design is the nut to=20
crack. My current problem is lack of knowledge regarding constraint=20
programming in general. Last week I must have read pretty much every=20
web-site that exists on the topic (at least it feels like it) and I=20
still struggle with understanding some concepts in this paradigm. The=20
vocabulary in use isn't exactly stream-lined with respect to users like=20
me (fairly good programmer, suck at anything even remotly related to=20
math). But to be honest, most of this feels like common sense, and most=20
of the algorithms aren't that hard to grasp, at least as long as you=20
don't have to invent them :-)

Thus I can't really fully answer your question regarding ILOG's=20
algorithms. But I can pretty much assure you that ILOG doesn't use=20
simple backtracking for their solvers. They do provide different search=20
schemes that one can use so it's hard to say exactly which one they use=20
for scheduling (or as they say, "you have to experiment with this since=20
their doesn't exists a determenistic way of choosing beforehand").
The one I currently use in JCL is a forward checking algorthm with full=20
arc consistency checking and dynamic variable ordering. However I'm not=20
completely happy with it's implementation so I'd be forced to=20
re-implement it. I'm not sure if this uses some sort of tabu search=20
(have to look closer at it) which would make it look pretty close to ASA=20
I guess. ASA however looks like a fairly simple algorithm (at least to=20
understand), is this observation correct or simply an illusion based on=20
good explanation in the paper?

But this is mearly a matter of style in the end. I want a CP package=20
that clearly separate solving from modelling. And I preferable want to=20
be able to model my problems using business domain objects (like=20
Activity, Resource, etc), and relation in business domain relations=20
(Activity.startAfterEnd(activity)). It looks like you have the same=20
intention even though you are tying it to ASA (which I can't really=20
figure out why). I'm not convinced that "completly different of what=20
conventional solvers offer" is 100% accurate. ILOG provides this with=20
business domain specific modelling API's (Scheduler, Dispatcher, Rules,=20
etc).

Anyway, I'll have a look at it, try to get it running, and see what=20
happens :-)

Cheers,
/Niclas

Florent Selva wrote:
> Hello,
>=20
> The ASA has been created with scheduling problems in mind=20
> (huge search
> space, great number of solutions). But is it suitable for your app ?
> Your can have a look at the Progressive Party Problem, a=20
> scheduling
> problem given as example.
> http://wasa.sourceforge.net/content/samples/index.htm
> http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/wasa/wasa/src/fr/
> jussieu/gla/wasa/samples/party/
>=20
> If the API looks good (completly different of what conventional=20
> solvers
> offer) you can try a mockup with it. Since you say that you can code=20
> a solver of yours in  2 weeks, a mockup using WASA should not=20
> take more=20
> than 2 days. We believe that 2 weeks is *very* optimistic but we=20
> don't=20
> know how fast you can code.
> WASA will probably give you bad results first (like pure random),=20
> just be aware that this algorithm needs lots of tuning.=20
> WASA is almost a platform for ASA tuning (even if doco don't say it=20
> much).=20
> Please be aware that WASA is *not optimized at all*, delivering=20
> poor=20
> performances and sucking lots of memory. But it should help=20
> before coding=20
> the optimized solution. ASA algorithm is much more subtle than it=20
> seems=20
> at first (and even second, and third) glance. You've been warned.
>=20
> One major issue for you is to estimate which kind of algorithm you=20
> need.=20
> If your ILOG product was using standard backtracking with good=20
> results,=20
> we advise you to stay inside this algorithm family and forget about=20
> WASA.
> We don't want our first potential alpha-tester to get stuck by our=20
> fault.
>=20
> Regards.
>=20
> The WASA team
> =20
> ------------------------------------
>=20
> Niclas Olofsson wrote:
>=20
>=20
>>Thanks guys. I'll subscribe as soon as it is up.
>>
>>Problems we want to solve is pretty much standard scheduling=20
>=20
> and=20
>=20
>>dispatching problems, with a little bit of focus on real-time (at=20
>=20
> least=20
>=20
>>the dispatching).
>>
>>Currently I'm working with the source from JCL but I'm writing a=20
>>completely new solver that can manage non-binary constaints=20
>=20
> (like=20
>=20
>>all_different(var[]). I also plan to extend it with basic constraint=20
>>arithmetics (+/-*) with some sort of propagation mechanism.
>>
>>But, I only have 2-3 weeks to do it and I've just spent a week=20
>=20
> learning=20
>=20
>>all I can about implementing solvers, API's, consistency=20
>=20
> checking,=20
>=20
>>propagation mechanisms, etc. And it sort of grows on you,=20
>=20
> doesn't it.=20
>=20
>>The result is most likely to be released open source at a later=20
>=20
> point=20
>=20
>>(whenever I feel it's mature enough).
>>But then I found WASA and figured that perhaps it is tangent.=20
>=20
> However,=20
>=20
>>it seems like you will focus on only one particaluar solver type=20
>=20
> while=20
>=20
>>I'd rather focus on several (like JCL does). But that's not too=20
>>important if it solves my problem in an effecient way :-)
>>
>>I'll read some more about ASA and see if I can figure that one=20
>=20
> out.
>=20
>>Cheers,
>>/Niclas
>>
>>Florent Selva wrote:
>>
>>>Hello,
>>>
>>>Following to your demand, we created two mailing list=20
>>>on SourceForge :
>>>was...@li...
>>>was...@li...
>>>It is said it will take 6-24 hours for activation.
>>>We expect you to repost your message to wasa-users=20
>>>list.
>>>
>>>Could you tell a bit more about the kind of
>>>projects you need to solve ? This is very *important*
>>>because WASA focuses only on the Adaptative Search=20
>>>Algorithm, which fits only to a certain class of=20
>>>problems, those which make conventional solvers=20
>>>(like Ilog Rules) collapsing under combinatory=20
>>>effect. This algorithm is not suitable for all=20
>>>problems, however.
>>>
>>>
>>>Regards
>>>
>>>The WASA team
>>>
>>>----------------------------------------------------------------------=
---------------
>>
> ---
>=20
>>>On Tuesday, August 6, 2002, at 08:28 PM, Niclas Olofsson=20
>>
> wrote:
>=20
>>>
>>>>Howdy,
>>>>
>>>>I looking for a CSP solver with optimization for Java. We are=20
>>>
>>>using ILOG=20
>>>
>>>
>>>>stuff, but want to find a cheaper and easier to use alternative.=20
>>>
>>>While=20
>>>
>>>
>>>>searching I stumbled on WASA. I'm no expert in CSP but know=20
>>>
>>>my way=20
>>>
>>>
>>>>around Java. I'd like to contribute if possible. Do you have a=20
>>>
> mail-
>=20
>>>list=20
>>>
>>>
>>>>somehwere?
>>>>
>>>>Cheers,
>>>>/Niclas
>>>>
>>>>
>>>


--=20
Niclas Olofsson - http://www.ismobile.com
Product Development, isMobile, Aurorum 2, S-977 75 Lule=E5, Sweden
Phone: +46(0)920-75550
Mobile: +46(0)70-3726404