<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#ffffff">
<br>
<br>
Op 19-10-11 14:16, Guilherme Kunigami schreef:
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
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>
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.<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
type="cite">
<div>
<br>
</div>
<div>[2] Do it using drools rules, like the following:</div>
<div><br>
</div>
<div><font class="Apple-style-span" face="'courier new',
monospace">rule "Avoid conflicting activities"</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace">when </font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>Assignment($room1:
room, $act1: activity, $id : <a moz-do-not-send="true"
href="http://activity.id" target="_blank">activity.id</a>)</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>Assignment(room
== $room1, room!= null, $act2 : activity, <a
moz-do-not-send="true" href="http://activity.id"
target="_blank">activity.id</a> > $id)</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>eval(Activity.conflict($act1,
$act2))</font></div>
</blockquote>
Why calculate it every time if you can cache it? [3]<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
type="cite">
<div><font class="Apple-style-span" face="'courier new',
monospace">then</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>insertLogical(new
IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"> 10, null));</font></div>
<div><font class="Apple-style-span" 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>
[3]<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
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>
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.<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>
<div><font class="Apple-style-span" face="'courier new',
monospace">rule "Avoid conflicting activities"</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace">when </font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>Assignment($room1
: room, $act1: activity, $id : <a moz-do-not-send="true"
href="http://activity.id/" target="_blank">activity.id</a>)</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>Assignment(room==
$room1, room != null, $act2 : activity, <a
moz-do-not-send="true" href="http://activity.id/"
target="_blank">activity.id</a> > $id)</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>Conflict(act1
== $act1, act2 == $act2)</font></div>
</div>
</blockquote>
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).<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
type="cite">
<div>
<div><font class="Apple-style-span" face="'courier new',
monospace">then</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"><span style="white-space: pre-wrap;"> </span>insertLogical(new
IntConstraintOccurrence("conflictingActivities",
ConstraintType.NEGATIVE_HARD,</font></div>
<div><font class="Apple-style-span" face="'courier new',
monospace"> 10, null));</font></div>
<div><font class="Apple-style-span" 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>
[3] is definitely faster than [2].<br>
<blockquote
cite="mid:CAK0MeX7vrs99zthk34OuS4ifaiFV-jY5BDNTdFRhA7GLAS2CNA@mail.gmail.com"
type="cite">
<div><br>
</div>
<div>Thanks!</div>
<pre wrap="">
<fieldset class="mimeAttachmentHeader"></fieldset>
_______________________________________________
rules-users mailing list
<a class="moz-txt-link-abbreviated" href="mailto:rules-users@lists.jboss.org">rules-users@lists.jboss.org</a>
<a class="moz-txt-link-freetext" href="https://lists.jboss.org/mailman/listinfo/rules-users">https://lists.jboss.org/mailman/listinfo/rules-users</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
With kind regards,
Geoffrey De Smet</pre>
</body>
</html>