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)

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

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

-- 
With kind regards,
Geoffrey De Smet

_______________________________________________
rules-users mailing list
rules-users@lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users