5:10 a.m.
Hello,
Here is a copy of a question I just sent on Stackoverflow :
http://stackoverflow.com/questions/13753983/is-drools-suitable-for-prepro...
I have a quite big resource allocation problem to compute.
I have just discovered Drools and I would like to know if it is a good
candidate to work as a preprocessor and generate a list of forbidden
allocations, based on some user rules.
The ProblemI have an optimisation engine that can allocate some activities
to some resources, while optimizing some KPIs (Key Performance Indicator).
The optimizer takes as input (among others) a list of forbiden allocations
that should be generated based on some user-provided rules.
Each forbid rule is an "AND" composition of two rules:
One for the activity
One for the resource
Each sub rule is itself a list of "AND" tests on some attributes.
Here is the structure of one rule, in Pseudo-Code
Rule1:
* ActivityRule
* activity.prop1 == "foo" AND
* activity.prop2 == "bar" AND
* ...
* ResourceRule
* resource.prop3 == "foobar" AND
* resource.prop4 == "NULL" AND
* ...
Rule2:
...
As soon as a pair of [Activity,Resource] matches one rule, it should be
sent as output, and not tested again against other rules.
Also, this is important to note that some rules will match very often,
while overs will match very rarely (very specific cases).
Performance constraints
Here are some rough hints about the volumetry of the problem :
* 1000 activities
* 200 resources
* 50 rules
I need the forbidden allocations to be generated in under a minute.
The challengeAs far, as I understand, Drools can surely generate those
forbidden allocations. the question is : "How smart is he" ?
If I had to write an engine myself for this particular problem, I would
make some improvements :
For example, I would not generate all possible allocations (200.000) and
then try to apply each rule on it (50 rules x 200.000).
Instead, I would try to match the resources and the activities separately
on each rule (each side of the rule), and then assemble the couples that
match at least one common rule.
Also, I would add some counter on each rule that would auto increment upon
each match, in order to apply first the rules that match often.
QuestionsIs the engine of Drools smart enought for that ? Or is he even
smarter ?
Do you have an example of Drools being used in a similar problem with
success ?
Do you have some hints on how to modelise this problem in Drools ?
Thanks in advance for your advice.
5:33 a.m.
I don't see any reason why Drools should not be capable of
handling this kind of problem. Some consideration should be
given to the way the rules are written, depending on the number
of constraints matching the properties: the ones reducing the
number of possible matches most should come first in the
rule. Possibly it is the Resource that should precede the
Activity, but of course this depends on the constraints.
-W
On 07/12/2012, Raphael Jolivet <raphael.jolivet(a)gmail.com> wrote:
Hello,
Here is a copy of a question I just sent on Stackoverflow :
http://stackoverflow.com/questions/13753983/is-drools-suitable-for-prepro...
I have a quite big resource allocation problem to compute.
I have just discovered Drools and I would like to know if it is a good
candidate to work as a preprocessor and generate a list of forbidden
allocations, based on some user rules.
The ProblemI have an optimisation engine that can allocate some activities
to some resources, while optimizing some KPIs (Key Performance Indicator).
The optimizer takes as input (among others) a list of forbiden allocations
that should be generated based on some user-provided rules.
Each forbid rule is an "AND" composition of two rules:
One for the activity
One for the resource
Each sub rule is itself a list of "AND" tests on some attributes.
Here is the structure of one rule, in Pseudo-Code
Rule1:
* ActivityRule
* activity.prop1 == "foo" AND
* activity.prop2 == "bar" AND
* ...
* ResourceRule
* resource.prop3 == "foobar" AND
* resource.prop4 == "NULL" AND
* ...
Rule2:
...
As soon as a pair of [Activity,Resource] matches one rule, it should be
sent as output, and not tested again against other rules.
Also, this is important to note that some rules will match very often,
while overs will match very rarely (very specific cases).
Performance constraints
Here are some rough hints about the volumetry of the problem :
* 1000 activities
* 200 resources
* 50 rules
I need the forbidden allocations to be generated in under a minute.
The challengeAs far, as I understand, Drools can surely generate those
forbidden allocations. the question is : "How smart is he" ?
If I had to write an engine myself for this particular problem, I would
make some improvements :
For example, I would not generate all possible allocations (200.000) and
then try to apply each rule on it (50 rules x 200.000).
Instead, I would try to match the resources and the activities separately
on each rule (each side of the rule), and then assemble the couples that
match at least one common rule.
Also, I would add some counter on each rule that would auto increment upon
each match, in order to apply first the rules that match often.
QuestionsIs the engine of Drools smart enought for that ? Or is he even
smarter ?
Do you have an example of Drools being used in a similar problem with
success ?
Do you have some hints on how to modelise this problem in Drools ?
Thanks in advance for your advice.
6:30 p.m.
Hi
I did not get the use case here.
When you write :
The Problem : I have an optimisation engine that can allocate some
activities
to some resources, while optimizing some KPIs (Key Performance Indicator).
The optimizer takes as input (among others) a list of forbiden allocations
that should be generated based on some user-provided rules.
to me you mean "generating an allocation plan".
drools-planner is for you, especially if your users want to define more complex rules.
As soon as a pair of [Activity,Resource] matches one rule, it should
be
sent as output, and not tested again against other rules.
Also, this is important to note that some rules will match very often,
while overs will match very rarely (very specific cases).
and here it sounds like a service that has a stream to consume ?
then just write rules, put a session in a separate thread, and send him your stream as
input.
You can even use drools-fusion time operators.
Performance constraints
Here are some rough hints about the volumetry of the problem :
* 1000 activities
* 200 resources
* 50 rules
I need the forbidden allocations to be generated in under a minute.
is it the due time for you plan ?
or each minute, you need to check 1000a and 200r ?
For example, I would not generate all possible allocations (200.000)
and
then try to apply each rule on it (50 rules x 200.000).
not 200000 obj, but 200000
binary variables.
Use local search (drools-planner) or other methods (depends on your KPIs).
if stream processing, processing 200.000 objects with 50 rules within a minute is not so
hard (depends on rules as W. said).
Instead, I would try to match the resources and the activities
separately
on each rule (each side of the rule), and then assemble the couples that
match at least one common rule.
RETE will do that for you
Also, I would add some counter on each rule that would auto increment
upon
each match, in order to apply first the rules that match often.
If there is a session in a thread, ie maintaining its kownledge over time,
RETE will do that for you, by propagating only the updates to the matching rules (forward
chaining).
If you speak about optimisation using local search, drools-planner will do that for you
(by using the previous, may be with adding so custom moves generators).
QuestionsIs the engine of Drools smart enought for that ? Or is he
even
smarter ?
If the point is to process forbidden associations, yes, drools can be
smarter than that.
I whould even say that drools shoud be used only if you want to do to more than that.
Do you have an example of Drools being used in a similar problem
with
success ?
optim : drools-planner and its cloud balancing sample
real-time stream : look at drools-fusion samples and also drools-expert doc (to get the
basis of what rules can do)
4:32 a.m.
Thanks very much for this detailled anbwser.
this helps me much.
I am currently playing with Drools, and trying to build rules in Java from
my own Rule objects, with the help of the lang.api.
Here are some comments in the flow of your anwsers
> The optimizer takes as input (among others) a list of forbiden
allocations
> that should be generated based on some user-provided rules.
to me you mean "generating an allocation plan".
drools-planner is for you, especially if your users want to define more
complex rules.
Actually, there is a optimization-team that already worked on that and came
up with their own solution.
They also evaluated Drool-planner for the "planning" part but went another
direction for several reasons.
I am only working here into transforming the complex user-filled rules into
"forbid" pairs as an input
to the optimizer.
I might use drools-planner for this.
and here it sounds like a service that has a stream to consume ?
then just write rules, put a session in a separate thread, and send him
your stream as input.
You can even use drools-fusion time operators.
No a stream, but yes, this is a service that will stay up and act as a
method :
Return the list of forbids for a given list of activities and resources.
I will pretty much build a knowledge base, and then, from time to time,
feed it with data, fire the rules and
look for forbid pairs.
Performance constraints
> Here are some rough hints about the volumetry of the problem :
> * 1000 activities
> * 200 resources
> * 50 rules
>
> I need the forbidden allocations to be generated in under a minute.
is it the due time for you plan ?
This is a due time, for an acceptable response time to the user.
> Instead, I would try to match the resources and the activities separately
> on each rule (each side of the rule), and then assemble the couples that
> match at least one common rule.
RETE will do that for you
> Also, I would add some counter on each rule that would auto increment
upon
> each match, in order to apply first the rules that match often.
If there is a session in a thread, ie maintaining its kownledge over time,
RETE will do that for you, by propagating only the updates to the
matching
rules (forward chaining).
Not sure if I get it.
If I have two rule A and B that may produce the same forbid pairs, I want
to produce this pair only once.
For that, I will use inference and produce a :
insert(new Forbid(ressource, activity))
Then, in each rule, I will check that this forbid is not already present.
So my question is :
Will Drools "learn" from preivous processings and "learn" that rule A
matches more often than rule B ? And so will it promote A to be processed
first ?
Even if I flush the working memory between two calls ?
If you speak about optimisation using local search, drools-planner
will do
that for you (by using the previous, may be with adding so custom moves
generators).
> QuestionsIs the engine of Drools smart enought for that ? Or is he even
> smarter ?
If the point is to process forbidden associations, yes, drools can be
smarter than that.
I whould even say that drools shoud be used only if you want to do to more
than that.
Hmm, yes, this is the dilemma :
I think that, for this particular problem, I could write an algorithm
myself.
I am trying to understand how Drools works in its guts, to foresee if
it is a good investment for the future.
For example, we are beginning to think about neighborhood forbids,
to forbid pairs of allocations <<Res1, Act1>, <Res2, Act2>> ...
Do you have an example of Drools being used in a similar problem
with
> success ?
optim : drools-planner and its cloud balancing sample
real-time stream : look at drools-fusion samples and also drools-expert
doc (to get the basis of what rules can do)
Thanks for those hints.
Brgds,
Raphael
3:57 a.m.
Hi Raphael,
There are multiple concerns mixed here, I don't know if this post would benefit of
being cutted in at least 2 :
1- How drools works : read about RETE algorithm (wikipedia is a good start) and about
drools-expert (core module that contains the engine, first chapter of the doc explain
various things about how it works, how you shoud use, and when you should use or not rules
engines).
2- How to mix rules (written by business users I guess) with another optimisation module?
For that point the solution will be some architectural design to be as much efficient as
possible to stay within the 1 minute. It is highly dependant of what you are using in the
optimisation module (especially the KPI form), and/or if you need to call the rules in the
middle of solving of not.
So, let's go with you case :
I am currently playing with Drools, and trying to build rules in Java
from my own Rule objects, with the help of the lang.api.
So you have your own Rule list somewhere.
You don't plan to use drools langage to define them ?
What they look like ? (if you can share at least the structure)
Actually, there is a optimization-team that already worked on that
and came up with their own solution.
They also evaluated Drool-planner for the "planning" part
but went another direction for several reasons.
This would be interresting to know these reasons.
I am only working here into transforming the complex user-filled rules
into "forbid" pairs as an input
to the optimizer.
I might use drools-planner for this.
Don't use planner only to generate pairs. You don't need planner there, drools
'basic' will do the job .
If you use planner, use it for you whole optim problem, and feed it with all yours
"complex user-filled rules".
Using planner for that will let you write at most any kind of criteria/KPI or contraints.
NoT a stream, but yes, this is a service that will stay up and act as
a method :
Return the list of forbids for a given list of activities and resources.
If I have two rule A and B that may produce the same forbid pairs, I want to produce this
pair only once.
For that, I will use inference and produce a :
insert(new Forbid(ressource, activity))
Then, in each rule, I will check that this forbid is not already
present.
If the problem is generating a Set of Forbid pairs, you should conlude your rules by
adding in a Set (in a kind of response object), and not inserting at all (and remove you
check in each rule, except If you use them for more than that).
So my question is :
Will Drools "learn" from preivous processings and "learn" that rule A
matches more often than rule B ?
And so will it promote A to be processed first ?
Even if I flush the working memory between two calls ?
Calling "fireAllRules" will fire all possible rules, whatever their execution
order.
It is not processed "by rules", see RETE algo.
Vincent
4164
days inactive
4169
days old
4 comments
3 participants
participants (3)
-
Raphael Jolivet -
Vincent LEGENDRE -
Wolfgang Laun