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