Re: [rules-users] [planner] Performance question
Op 19-10-11 14:16, Guilherme Kunigami schreef:
Consider I have a set of N activities with a given start and end
times
and I want to assign them to a set of rooms.
One of the main rules is to avoid two activities that have time
conflicts, to be assigned to the same room. I devised three modelling
options:
[1] Do it entirely in Java code, checking whether there will be a
conflict before allowing an "Assignment move". This way, all solutions
that the algorithm works with are feasible.
In the manual that's called a
"build-in hard constraint". Look for it.
In this use case, that is probably a bad idea in my experience. Why?
Well I hope this makes any sense:
/You need to allow the optimization algorithms to break it now and then
to tunnel through a bad search space into another good search space./
If it doesn't, don't worry.
[2] Do it using drools rules, like the following:
rule "Avoid conflicting activities"
when
Assignment($room1: room, $act1: activity, $id : activity.id
<http://activity.id>)
Assignment(room == $room1, room!= null, $act2 : activity, activity.id
<http://activity.id> > $id)
eval(Activity.conflict($act1, $act2))
Why calculate it every time if you can cache
it? [3]
then
insertLogical(new IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,
10, null));
end
Here I'm using Assignment as the only planning entity. There's an
assignment for each activity and it may point to a room or to null in
the case the activity is not assigned. In the case above, I have a
static function that checks whether two activities conflicts. This
way, solutions may be infeasible but with high penalties the best
solution found will eventually be feasible.
[3]
I also thought of a third option, which is to insert a fact
"Conflict"
for each pair of conflicting activities in a preprocessing phase. This
way we would end up with:
This is the recommended way. It's called "cached
problem facts" in the
manual.
See the TopicConflict use in the examinationScoreRules.drl and
Examination.getProblemFacts() in the examples.
rule "Avoid conflicting activities"
when
Assignment($room1 : room, $act1: activity, $id : activity.id
<http://activity.id/>)
Assignment(room== $room1, room != null, $act2 : activity, activity.id
<http://activity.id/> > $id)
Conflict(act1 == $act1, act2 == $act2)
I would put Conflict first. But try it this
way too and let me know
which works better ;) I don't know.
Stated differently: Instead of checking every 2 simultaneous assignments
if they are a conflict,
I would check if every 2 conflict assignments are simultaneous (like in
examinationScoreRules.drl).
then
insertLogical(new IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,
10, null));
end
The problem is that there may be up to O(N^2) such objects.
I do not know the rules engine algorithm in depth, so I'd like to
know: Is any of these approaches more efficient than the others?
[3] is definitely
faster than [2].
Thanks!
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
Attachments:
- attachment.html (text/html — 7.9 KB)