|
From: Niclas O. <gu...@ac...> - 2002-08-12 16:45:40
|
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 |