[rules-users] [planner] Performance question

[Guilherme Kunigami]

2011/10/19 Geoffrey De Smet <ge0ffrey.spam at gmail.com>

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

Hmm, I think I understood it. Allowing infeasible solutions may help to
scape from local minima in the space of feasible solutions for example.


>
>
>  [2] Do it using drools rules, like the following:
>
>  rule "Avoid conflicting activities"
> when
>  Assignment($room1: room, $act1: activity, $id : activity.id)
>  Assignment(room == $room1, room!= null, $act2 : activity, 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)
>  Assignment(room== $room1, room != null, $act2 : activity, 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).
>
>
Ok! I will perform some stress tests to verify which one works better.

Thanks again,


>  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 listrules-users at lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.jboss.org/pipermail/rules-users/attachments/20111019/7c2f3da6/attachment.html