wasa-users — WASA users' mailing list

Re: [Wasa-users] Multiple Explorers

[Laurent C. <cai...@de...>]

> Just out of curiousity, what exactly does the "rank" 
> say. "instanciation rank of the Var" didn't make me 
> much smarter I'm afraid :-)

No, it is not smart at all. But in some cases it's very
handy. Please note that :
- it is intended to be used only when you've got 1
  sole array of Vars in your system,
- you're not bound to used getRank(). You can create 
  your own Vars, which provide a reference to the 
  buisness object member you wish to access to.


> I also have a question regarding cost functionality. 
> I need to implement something like "make min timespan".
> ...
> Any ideas? In general, how should one work with overal 
> costs?

You should create a Constraint "MinTimespan" which whould
increase error of all Vars implied in timespan calculation.
This is, at a certain point, the same thing as explaining
a solver what you want, and how vars are interrelated.

Re: [Wasa-users] Multiple Explorers

[Laurent C. <cai...@de...>]

I think that reusable Explorers and Constraints should be seen
as an extension of a buisness objects framework. That's because
WASA is designed to keep connected with buisness objects, and
avoid writing your buisness rules a second time, in the weird
language a solver understands. 

This would give 3 products at all : the buisness-oriented 
framework, WASA, and an adapter between both. In that way, 
we'll avoid unnecessary coupling.


> Florent Selva wrote:
> > In a classic CSP problem you need a specific domain 
> > for each kind of var: in WASA, you need a specific 
> > explorer for each kind of var to do the same thing.
> 
> Would it make sense to develop standard explorers and constraints like 
> you have in for example JSolver and JCL?
> 
> /Niclas

Re: [Wasa-users] Multiple Explorers

[Niclas O. <nic...@is...>]

Florent Selva wrote:
> In a classic CSP problem you need a specific domain for each kind of var: in 
> WASA, you need a specific explorer for each kind of var to do the same thing.

Would it make sense to develop standard explorers and constraints like 
you have in for example JSolver and JCL?

/Niclas

Re: [Wasa-users] Multiple Explorers

[Niclas O. <nic...@is...>]

I think I discovered the problem. I believe I missused the Var.getRank() 
method. I'll rework my code next week to something a little bit more 
stable and get back to you with some feedback on that.

Just out of curiousity, what exactly does the "rank" say. "instanciation 
rank of the Var" didn't make me much smarter I'm afraid :-)

I also have a question regarding cost functionality. I need to implement 
something like "make min timespan" on a schedule and I'm not quite sure 
how to implement this using WASA. If I use an "ordinary" solver I would 
probably iterate over a set of solutions while decrementing some cost 
var. I'd do that until I no long have a solution. I've done something 
similar using WASA, but figured that perhaps I could use constraints to 
do this for me instead. However, I can't really figure out how to do it. 
Any ideas? In general, how should one work with overal costs?

Cheers,
/Niclas

Re: [Wasa-users] Multiple Explorers

[Laurent C. <cai...@de...>]

Engine uses Constraints to evalutate Vars' overall error
on a given Configuration, then calls worst Var's Explorer
to attempt to find a better value. If Engine (in fact, the
wrapped Algorithm instance) detected that there was no
improvement, it calls the RandomConfigurator to shake
the Buisness Objects state.
In other words, Engine chooses the Var instance for you.
The Var instance knows its Explorer instance, so the Engine
knows which Explorer to call.

You shouldn't care about what is the worst var for each 
explorer : the selected Explorer in each step must be the 
one corresponding to the worst problem var. So, for this 
selected Explorer, "the worst domain var" and "the worst
problem var" are the same thing.
As in each step you only use one explorer (the worst problem 
var Explorer), nothing happens in others : you don't need 
to know what is the worst var for those other Explorers / 
domains.


I guess the getVar() method you talk about is :
protected final Explorer.getVar()
and you've set a trace or a breakpoint in your own
Explorer's explore() method. But this method can be called
by Engine or Algorithm or Configuration objects whenever
they need it. We'd better talk about hasNeighbours() and
explore() methods that you've defined in your own
Explorers. When in hasNeighbours() or explore(), the
getVar() method should return the correct Var instance.

So, only use getVar() in those two methods.

When you say "I expect (...) the currently worst variable
would be called from it's corresponding explorer" you're
right, and it *should* work like this. The explore()
method is a callback that Engine (in fact : Algorithm)
calls when it detects it is useful.
 
I don't understand what your problem is. Do you mean
that :
(1) getVar() called from hasNeighbours() or explore()
    returns an unexpected Var instance.
(2) one of your Explorers is never called.
 
Quick answers :
(1) Check how you created your Vars, since they're bound
    to an Explorer in their constructor.
(2) check your Constraints. Do they affect the right Var
    instance ?
 
Hope this will help.


The WASA Team

> 
> Ok, very good. Then I'm still on the right track I guess. I do exactly 
> what you describe, just that explorer "2" doesn't ever get called.
> 
> My problem then is that getVar() reports the currently worst variable in 
> the "wrong" explorer. I expect that the currently worst variable would 
> be called from it's corrensponding explorer, ie; the getVar() would 
> report the worst variable in the current (domain) explorer, not for all 
> of them. I would also expect that the explorer "called" would be the one 
> that contains the currently worst var. Somewhat confused, but I guess 
> that's a good thing :-)
> 
> /Niclas
> 
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by: OSDN - Tired of that same old
> cell phone?  Get a new here for FREE!
> https://www.inphonic.com/r.asp?r=sourceforge1&refcode1=vs3390
> _______________________________________________
> Wasa-users mailing list
> Was...@li...
> https://lists.sourceforge.net/lists/listinfo/wasa-users
> 
> 

Re: [Wasa-users] Multiple Explorers

[Niclas O. <nic...@is...>]

Ok, very good. Then I'm still on the right track I guess. I do exactly 
what you describe, just that explorer "2" doesn't ever get called.

My problem then is that getVar() reports the currently worst variable in 
the "wrong" explorer. I expect that the currently worst variable would 
be called from it's corrensponding explorer, ie; the getVar() would 
report the worst variable in the current (domain) explorer, not for all 
of them. I would also expect that the explorer "called" would be the one 
that contains the currently worst var. Somewhat confused, but I guess 
that's a good thing :-)

/Niclas

Re: [Wasa-users] Multiple Explorers

[Florent S. <se...@de...>]

Hi

In WASA, there is no domain concept. You never write something like: x in [1..5].
The domain concept is replaced by the explorer concept.

In a classic CSP problem you need a specific domain for each kind of var: in 
WASA, you need a specific explorer for each kind of var to do the same thing.

So, you can (and in fact you have to...) choose the explorer you want to use, for 
each var you create.

There is only 2 ways of creating vars in WASA, both specifying an appropriate 
explorer. When a var is chosen as the worst one during the problem solving, the 
selected explorer is the one you've declared at the var creation.

Here are the 2 ways of creating vars in WASA:

1) use the VarFactory by mapping a property of your business object:
    
    public class Queen {
      private int line;
      public Queen(...)...
      public void setLine( int line ) ...
      public int getLine() ...
    }

    then:
    
    Queen queen = new Queen(...);

    QueenExplorer queenExplorer = new QueenExplorer(...);

    Var theQueenLineVar = VarFactory.INSTANCE.createPropertyVar(
        queenExplorer , 
        queen , 
        "line" ) ;

As you can see, there is a specific explorer for this var.

see: http://wasa.sourceforge.net/content/cooksbook/index.htm 

2) inherit the Var abstract class in order to map a more complex business object.

public class QueenVar extends Var {

    ComplexQueen queen; //the mapped business object
    
    public QueenVar( ComplexQueen queen, Explorer explorer ) {
       super( explorer ) ;
       this.queen = queen;
    }

    ... all other methods to map the queen business object...
}

As you see... the Var constructor takes an Explorer in argument.
 
for the Var class, see:
http://wasa.sourceforge.net/javadoc-dev/fr/jussieu/gla/wasa/core/Var.html

the Progressive Party Problem uses this technique for the ScheduleVar. See:
http://wasa.sourceforge.net/javadoc-dev/fr/jussieu/gla/wasa/samples/party/
package-summary.html

There isn't a lot of doc about this...

Regards

The Wasa Team

> Howdy guys,
> 
> Here is a question for you :-)
> 
> I have a couple of vars and would like to have multiple exploreres, one 
> for each type of business objects (ActivityExplorer, ResourceExplorer, 
> etc). Is this possible at all?
> 
> If this doesn't make sense to you (having multiple explorers) I'd be 
> happy to explain what I want to achive instead, but that'll take me some 
> time so I thought I'd start with an out of context question instead.
> 
> Cheers,
> /Niclas
> 
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by: OSDN - Tired of that same old
> cell phone?  Get a new here for FREE!
> https://www.inphonic.com/r.asp?r=sourceforge1&refcode1=vs3390
> _______________________________________________
> Wasa-users mailing list
> Was...@li...
> https://lists.sourceforge.net/lists/listinfo/wasa-users
> 
> 

[Wasa-users] Multiple Explorers

[Niclas O. <nic...@is...>]

Howdy guys,

Here is a question for you :-)

I have a couple of vars and would like to have multiple exploreres, one 
for each type of business objects (ActivityExplorer, ResourceExplorer, 
etc). Is this possible at all?

If this doesn't make sense to you (having multiple explorers) I'd be 
happy to explain what I want to achive instead, but that'll take me some 
time so I thought I'd start with an out of context question instead.

Cheers,
/Niclas

Re: [Wasa-users] Re: Re: WASA

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

Laurent Caillette wrote:
>>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).

I know more now. I've read about generic approaches, local 
searchmethods, etc.

> 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.

The honest feedback is that it's a programming disaster (to say the 
least), but works. I couldn't make sense of the algortithms implemented 
when comparing them to the psuedo code. So I trashed it and started on 
something new myself, sorry. I also like the way ILOG works with 
heuristics for instantiation so I have something like that now. I also 
like the propagation model ILOG uses so I added that. I used to do VRML 
earlier and the propagation works almost the same there, so I'm used to 
thinking in thouse terms. I'm also re-implementing all algorithms that I 
want, now using revertable objects. Might now be the fastest, but it 
sure makes it simple. I had the first algorithm, simple back tracking, 
working on this framework tow days ago now.

But I like WASA a lot, in fact I like it more than any other I've seen 
so far. My boss likes it too. So we are probably going to work out a 
model where we can use our own, WASA, or ILOG JSolver depending on what 
the case might be.

Cheers,
/Niclas

[Wasa-users] Re: Re: WASA

[Laurent C. <cai...@de...>]

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

[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

[Wasa-users] Testing mailing list.

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

Hi, just testing. If it works I'll follow up with earlier discussion.