<br><br><div class="gmail_quote">2011/10/19 Geoffrey De Smet <span dir="ltr"><<a href="mailto:ge0ffrey.spam@gmail.com">ge0ffrey.spam@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<u></u>
<div text="#000000" bgcolor="#ffffff">
<br>
<br>
Op 19-10-11 14:16, Guilherme Kunigami schreef:
<div class="im"><blockquote type="cite">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.
<div><br>
</div>
<div>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:</div>
<div><br>
</div>
<div>[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.</div>
</blockquote></div>
In the manual that's called a "build-in hard constraint". Look for
it.<br>
<br>
In this use case, that is probably a bad idea in my experience. Why?
Well I hope this makes any sense:<br>
<i>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.</i><br>
If it doesn't, don't worry.</div></blockquote><div><br></div><div>Hmm, I think I understood it. Allowing infeasible solutions may help to scape from local minima in the space of feasible solutions for example.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div text="#000000" bgcolor="#ffffff"><div class="im"><br>
<blockquote type="cite">
<div>
<br>
</div>
<div>[2] Do it using drools rules, like the following:</div>
<div><br>
</div>
<div><font face="'courier new',
monospace">rule "Avoid conflicting activities"</font></div>
<div><font face="'courier new',
monospace">when </font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>Assignment($room1:
room, $act1: activity, $id : <a href="http://activity.id" target="_blank">activity.id</a>)</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>Assignment(room
== $room1, room!= null, $act2 : activity, <a href="http://activity.id" target="_blank">activity.id</a> > $id)</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>eval(Activity.conflict($act1,
$act2))</font></div>
</blockquote></div>
Why calculate it every time if you can cache it? [3]<div class="im"><br>
<blockquote type="cite">
<div><font face="'courier new',
monospace">then</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>insertLogical(new
IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,</font></div>
<div><font face="'courier new',
monospace"> 10, null));</font></div>
<div><font face="'courier new',
monospace">end </font></div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
</blockquote></div>
[3]<div class="im"><br>
<blockquote type="cite">
<div>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:</div>
</blockquote></div>
This is the recommended way. It's called "cached problem facts" in
the manual.<br>
See the TopicConflict use in the examinationScoreRules.drl and
Examination.getProblemFacts() in the examples.<div class="im"><br>
<blockquote type="cite">
<div><br>
</div>
<div>
<div><font face="'courier new',
monospace">rule "Avoid conflicting activities"</font></div>
<div><font face="'courier new',
monospace">when </font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>Assignment($room1
: room, $act1: activity, $id : <a href="http://activity.id/" target="_blank">activity.id</a>)</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>Assignment(room==
$room1, room != null, $act2 : activity, <a href="http://activity.id/" target="_blank">activity.id</a> > $id)</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>Conflict(act1
== $act1, act2 == $act2)</font></div>
</div>
</blockquote></div>
I would put Conflict first. But try it this way too and let me know
which works better ;) I don't know.<br>
Stated differently: Instead of checking every 2 simultaneous
assignments if they are a conflict,<br>
I would check if every 2 conflict assignments are simultaneous (like
in examinationScoreRules.drl).<div class="im"><br></div></div></blockquote><div><br></div><div>Ok! I will perform some stress tests to verify which one works better.</div><div><br></div><div>Thanks again,</div><div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div text="#000000" bgcolor="#ffffff"><div class="im">
<blockquote type="cite">
<div>
<div><font face="'courier new',
monospace">then</font></div>
<div><font face="'courier new',
monospace"><span style="white-space:pre-wrap"> </span>insertLogical(new
IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,</font></div>
<div><font face="'courier new',
monospace"> 10, null));</font></div>
<div><font face="'courier new',
monospace">end </font></div>
</div>
<div><br>
</div>
<div>The problem is that there may be up to O(N^2) such objects. </div>
<div><br>
</div>
<div>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?</div>
</blockquote></div>
[3] is definitely faster than [2].<br>
<blockquote type="cite">
<div><br>
</div>
<div>Thanks!</div>
<pre><fieldset></fieldset>
_______________________________________________
rules-users mailing list
<a href="mailto:rules-users@lists.jboss.org" target="_blank">rules-users@lists.jboss.org</a>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a>
</pre>
</blockquote><font color="#888888">
<br>
<pre cols="72">--
With kind regards,
Geoffrey De Smet</pre>
</font></div>
<br>_______________________________________________<br>
rules-users mailing list<br>
<a href="mailto:rules-users@lists.jboss.org">rules-users@lists.jboss.org</a><br>
<a href="https://lists.jboss.org/mailman/listinfo/rules-users" target="_blank">https://lists.jboss.org/mailman/listinfo/rules-users</a><br>
<br></blockquote></div><br>