[rules-users] [planner] Performance question

[Geoffrey De Smet]

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 at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users

-- 
With kind regards,
Geoffrey De Smet

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20111019/d16ae8f8/attachment.html