tag:blogger.com,1999:blog-83761566115301798692024-03-21T03:58:41.450-07:00CodeCandiesdblcdbluhttp://www.blogger.com/profile/00454452258805862472noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8376156611530179869.post-6089528733323410502012-10-30T13:07:00.000-07:002012-10-30T13:09:25.516-07:00Do Christmas Present Decisions based on ILPs<div>
</div>
<div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">I have a
very large family which means that every year for Christmas many persons are
forced to buy many presents for other members of my family. Thus, about
fifteen years someone within my family had the idea that everybody should not
gift a present to anybody else any longer but to only one person each year. </span></div>
<div class="MsoNormal" style="text-align: justify;">
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">The idea
got adopted and thus, since then, every year, every person in my family has to
buy a present for only one person within the whole family. The complicate
thing with this solution is that somebody has to decide which person has to buy
a present for which person each year. This sounds easy at first, as a simple
draw could solve the problem. However, there are some additional constraints
that make the process more complicate:</span></div>
</div>
<ol align="justify">
<li class="MsoNormal"><span lang="EN-US" style="mso-ansi-language: EN-US;">First, each
person should get exactly one gift.</span></li>
<li>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Second,
some combinations are excluded. For example, my mother will always buy a
present for my father and I will buy a present for my mother as well which
should forbid these combinations for the draw.</span></div>
</li>
<li>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Third, it
should be avoided that a person has to buy a present for the same person as in
the last year. Ideally, every person should have to buy a present for a person
it never gift a present before.</span></div>
</li>
</ol>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: justify;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBNqKiHxLAq58Ob_x1oxKS8f-X8dWCnO6sewHcTBAXngYvtcC2KqIo1U9VeHHg_RiIyrHAN1dfeiHXCDulx7ROagr7OR11ESb1jDPEQg4Qe8qaMjpvGArzr2ze9pcMdABYs-4YYV4Ggik/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhBNqKiHxLAq58Ob_x1oxKS8f-X8dWCnO6sewHcTBAXngYvtcC2KqIo1U9VeHHg_RiIyrHAN1dfeiHXCDulx7ROagr7OR11ESb1jDPEQg4Qe8qaMjpvGArzr2ze9pcMdABYs-4YYV4Ggik/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A simple example for a family consisting of six members.</td></tr>
</tbody></table>
<div style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">To get this
more clearly let us look at an example: Imagine two sisters, both having a
husband and each one child. Thus, the family member group consists of two
cousins and their parents. A valid combination would be that</span></div>
<ul align="justify">
<li class="MsoListParagraphCxSpFirst" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Husband
1 buys a present for Aunt 2</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Aunt
1 buys a present for Child 2</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Child
1 buys a present for Husband 2</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Husband
2 buys a present for Aunt 1</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Aunt
2 buys a present for Child 1</span></li>
<li class="MsoListParagraphCxSpLast" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">Child
2 buys a present for Husband 1</span></li>
</ul>
<div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">The
constraints include:</span></div>
<ul align="justify">
<li class="MsoListParagraphCxSpFirst" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">No
present from Husband 1 for Aunt 1</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">No
present from Husband 1 for Child 1</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">No
present from Aunt 1 for Child 1</span></li>
<li class="MsoListParagraphCxSpMiddle" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">No
present from Aunt 1 for Aunt 2</span></li>
<li class="MsoListParagraphCxSpLast" style="text-indent: -18pt;"><span lang="EN-US" style="mso-ansi-language: EN-US;">…</span></li>
</ul>
<div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Somehow
someone in my family thought me to be the smartest guy (sorry family folks).
And thus, I had to draw all the combinations every year. Originally, I did a
simple draw every year and simply changed the drawn combinations until
everything worked right by changing combinations for up to two hours until all
the constraints were considered in the final result. However, over the years
more and more members of my family joined the one-present-per-family-member
idea and thus, today the draw includes presents and constraints for sixteen
family members, all of them having their personalized constraints!</span></div>
</div>
<div>
<span lang="EN-US" style="mso-ansi-language: EN-US;">As last
year a colleague of mine showed me integer linear programs (ILPs) [1] and how
they could be used to compute optimal solutions for constrained mathematical
problems, I had the idea to apply them for my Christmas present problem. And
this is what this article is about: how to compute Christmas present
combinations with ILPs.</span></div>
<div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify;">
</div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">How do ILPs
work? Actually they are quite simple. First, we define a set of variables for
which we want to compute an optimal solution (e.g., we can say we have to
variables <span style="font-family: "Courier New", Courier, monospace;">a</span> and <span style="font-family: "Courier New", Courier, monospace;">b</span> for which we want to compute integer values). Second, we
define an objective function (e.g., we can say that the sum of <span style="font-family: "Courier New", Courier, monospace;">a</span> and <span style="font-family: "Courier New", Courier, monospace;">b</span> should
be as small as possible). Third, we can define some constraints (e.g. that <span style="font-family: "Courier New", Courier, monospace;">a</span> is
<span style="font-family: "Courier New", Courier, monospace;">b-2</span> and <span style="font-family: "Courier New", Courier, monospace;">b</span> is <span style="font-family: "Courier New", Courier, monospace;">2*a</span>). Afterwards, an ILP solver will compute an optimal
solution for our ILP. In our example the optimal solution will be <span style="font-family: "Courier New", Courier, monospace;">a=2</span> and <span style="font-family: "Courier New", Courier, monospace;">b=4</span>.</span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify;">
</div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">So how does
an ILP solution for our example looks like? </span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">First, we
have to define our variables. For each valid combination of persons buying and
getting a present, we define a variable that can be either <span style="font-family: "Courier New", Courier, monospace;">0</span> or <span style="font-family: "Courier New", Courier, monospace;">1</span> indicating a
non-drawn or drawn combination. Thus, we need the following variables:
<span style="font-family: "Courier New", Courier, monospace;">aunt1_husband2, aunt1_child2, husband1_aunt2, husband1_husband2,
husband1_child2, child1_aunt2, child1_husband2, child1_child2, aunt2_husband1,
aunt2_child1, husband2_aunt1, husband2_husband1, husband2_child1, child2_aunt1,
child2_husband1, child2_child1</span>.</span></div>
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span>
<br />
<div class="MsoNormal">
</div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Next, we
have to specify our constraints. First, each person has to buy exactly one
present: For example, the constraint <span style="font-family: "Courier New", Courier, monospace;">husband1_aunt2 + husband1_husband2 +
husband1_child2 = 1</span> ensures that husband 1 will buy one present. We specify
such a rule for each member of the family. Afterwards, we have to define a
similar rule for each family member indicating that it will receive exactly one
present. For example, again husband 1: <span style="font-family: "Courier New", Courier, monospace;">aunt2_husband1 + husband2_husband1 +
husband2_child2 = 1</span>.</span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Following,
we have to consider that we want to avoid presents from the former years. Thus,
for each drawn person we define a cost function, which we afterwards try to
optimize (i.e., minimize) with our ILP. For each family member we define a cost
that consists of all former presents this member got before. For example, if
husband 1 got two presents from child 2 and one present from aunt 2 before, its
cost function will be: <span style="font-family: "Courier New", Courier, monospace;">cost_husband1 = 2 child2_husband1 + aunt2_husband1</span>.</span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal" style="text-align: justify;">
</div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Finally, we
have to specify our objective function which is simply to minimize the cost of
former presents: <span style="font-family: "Courier New", Courier, monospace;">min cost_aunt1 + cost_husband1 + cost_child1 + cost_aunt2 +
cost_husband2 + cost_child2.</span></span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;"><br /></span></span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;">And we are
done. Our whole program looks as shown below (if we consider no former
presents):</span></div>
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span>
<br />
<div class="MsoNormal" style="text-align: justify;">
</div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* Objective function */</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">min: cost_Aunt1 + cost_Husband1 + cost_Child1 + cost_Aunt2 +
cost_Husband2 + cost_Child2;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* Constraints */</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* One customer per guy. */</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt1_Husband2 + Aunt1_Child2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Husband1_Aunt2 + Husband1_Husband2 + Husband1_Child2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Child1_Aunt2 + Child1_Husband2 + Child1_Child2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt2_Husband1 + Aunt2_Child1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Husband2_Aunt1 + Husband2_Husband1 + Husband2_Child1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Child2_Aunt1 + Child2_Husband1 + Child2_Child1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* One present per guy. */</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Husband2_Aunt1 + Child2_Aunt1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt2_Husband1 + Husband2_Husband1 + Child2_Husband1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt2_Child1 + Husband2_Child1 + Child2_Child1 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Husband1_Aunt2 + Child1_Aunt2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt1_Husband2 + Husband1_Husband2 + Child1_Husband2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">Aunt1_Child2 + Husband1_Child2 + Child1_Child2 = 1;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* Cost per customer. */</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Aunt1 = 0;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Husband1 = 0;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Child1 = 0;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Aunt2 = 0;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Husband2 = 0;</span></span></div>
<div style="text-align: left;">
<span style="font-family: "Courier New", Courier, monospace;">
</span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0pt; text-align: left;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Child2 = 0;</span></span></div>
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiw43RGxAaxnnGUeEtqA3hIVuqM85URMWbrXRNumXYBCUWLxUCEas4AGCMz2M3r3E8rb6L6Uhs2zh-4UETXRpWGVcOu1oecZRETITb_eougXThgrUTYbpCVegCdoSYMaOuNiHbtr2RLE4o/s1600/example.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"></a></div>
<div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Now, we can
use an ILP solver to solve the problem. Here, we use the LPSolve IDE that can
be obtained from [2]. By solving the ILP the get the following result:</span></div>
<div class="MsoNormal" style="text-align: justify;">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_8WKqYun_RyO8DWOuaMOjTIknYg_n_5ctkqC-XbtFIjGS8_1BRvcRUsaklQKgfyyse2ZK2SJp4E4HkH5rGe0-cRW4QlKJ-qZc_lZSPvMwg56AYRI48zGdpid0PwtE9U4t9p_wLslSQOo/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi_8WKqYun_RyO8DWOuaMOjTIknYg_n_5ctkqC-XbtFIjGS8_1BRvcRUsaklQKgfyyse2ZK2SJp4E4HkH5rGe0-cRW4QlKJ-qZc_lZSPvMwg56AYRI48zGdpid0PwtE9U4t9p_wLslSQOo/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">ILP solving result.</td></tr>
</tbody></table>
<div class="MsoNormal" style="text-align: justify;">
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Thus:</span></div>
<ul>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Aunt1
buys a present for Child2</span></div>
</li>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Husband1
buys a present for Husband2</span></div>
</li>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Child1
buys a present for Aunt2</span></div>
</li>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Aunt1
buys a present for Child1</span></div>
</li>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Husband2
buys a present for Husband1</span></div>
</li>
<li><div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Child2
buys a present for Aunt1</span></div>
</li>
</ul>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">If we want
to compute the combinations of the following year, we simple have to add last
year’s combinations, by altering the costs to:</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-autospace: none;">
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">/* Cost per customer. */</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Aunt1 = Aunt1_Child2;</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Husband1 = Husband1_Husband2;</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Child1 = Child1_Aunt2;</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Aunt2 = Aunt2_Child1;</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Husband2 = Husband2_Husband1;</span></span><br />
<span lang="EN-US" style="color: black; font-family: Consolas; font-size: 10.0pt; line-height: 115%; mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;">cost_Child2 =
Child2_Aunt1;</span></span></div>
<span style="font-family: "Courier New", Courier, monospace;">
</span><br />
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><span style="font-family: "Courier New", Courier, monospace;"><br /></span></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">And we get
a new valid and optimal combination.</span></div>
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">The
attentive reader may have noticed that the number of constraints to be
formulated increases squared with every additional family member. Furthermore,
I mentioned that our present group currently includes sixteen participants.
Formulating such an ILP by hand is both cumbersome and error-prone.</span></div>
</div>
<div class="MsoNormal">
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span>
<span lang="EN-US" style="mso-ansi-language: EN-US;">Thus, this
year, I implemented a simple DSL using Eclipse and EMFText [3] to formulate the
problem in a more elegant way:</span></div>
</div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUrbbED225ewpkIwYbXc08fsnKg2VKsRIkg9pkWF0ebWOtCBJP2iXNI6H1sOAbjuQko2iGcGN2y4S3IE4GfuJp_xNOmnNF9Kpj_FQCzIjLraAOnBmznzW8LuSmR35xwObXo9tm6M0B6zk/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhUrbbED225ewpkIwYbXc08fsnKg2VKsRIkg9pkWF0ebWOtCBJP2iXNI6H1sOAbjuQko2iGcGN2y4S3IE4GfuJp_xNOmnNF9Kpj_FQCzIjLraAOnBmznzW8LuSmR35xwObXo9tm6M0B6zk/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Formulation of the present problem in a simple DSL.</td></tr>
</tbody></table>
<div class="MsoNormal">
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">The DSL is
more or less self-explanatory. First, we define all members of the family.
Afterwards, we define exclusion constraints for invalid combinations. The DSL allows
directed exclusions. Thus, both <span style="font-family: "Courier New", Courier, monospace;">a conflicts b</span> and <span style="font-family: "Courier New", Courier, monospace;">b conflicts a</span> have to be
defined for undirected exclusions. Finally, past present combinations can be
specified.</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Afterwards,
the Eclipse plugin will generate the respective ILP, triggers the ILP solver
and will propagate back the valid solution:</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbcxJKUMzhre7hd0AimaHVzoGhIuTXwqcKmkH6LKl3Tv90uyUPd5U1yl23N5HBPbhhExpGFkuYM7T1WabKKXRmWVJdJ8_R2A_Iz4IaY2Vi-n3BW-bzFUS0ovhXCQ3g_bGwFwVxq4mcvZ0/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjbcxJKUMzhre7hd0AimaHVzoGhIuTXwqcKmkH6LKl3Tv90uyUPd5U1yl23N5HBPbhhExpGFkuYM7T1WabKKXRmWVJdJ8_R2A_Iz4IaY2Vi-n3BW-bzFUS0ovhXCQ3g_bGwFwVxq4mcvZ0/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Triggering ILP solving from the DSL.</td></tr>
</tbody></table>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibKccPd4mLfZDmO0H66uJz_cvH8iNbWaTnS-ngxlnYpMBzBe3Yvx_HBJLHfoq0islfQ5B5d89CyJL8keqN3YYwquQo-2XF0fCCeHe0JbRNnYz9wd87AwwZgb0NdS-1sAdWRtNIyka1fkA/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibKccPd4mLfZDmO0H66uJz_cvH8iNbWaTnS-ngxlnYpMBzBe3Yvx_HBJLHfoq0islfQ5B5d89CyJL8keqN3YYwquQo-2XF0fCCeHe0JbRNnYz9wd87AwwZgb0NdS-1sAdWRtNIyka1fkA/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Result of the ILP solving.</td></tr>
</tbody></table>
<div class="MsoNormal">
</div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">Finally, the implemented tooling can automatically add the newly computed solution to the program’s past
presents rules to save the result within the program for the next year’s
computation:</span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiw43RGxAaxnnGUeEtqA3hIVuqM85URMWbrXRNumXYBCUWLxUCEas4AGCMz2M3r3E8rb6L6Uhs2zh-4UETXRpWGVcOu1oecZRETITb_eougXThgrUTYbpCVegCdoSYMaOuNiHbtr2RLE4o/s1600/example.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiw43RGxAaxnnGUeEtqA3hIVuqM85URMWbrXRNumXYBCUWLxUCEas4AGCMz2M3r3E8rb6L6Uhs2zh-4UETXRpWGVcOu1oecZRETITb_eougXThgrUTYbpCVegCdoSYMaOuNiHbtr2RLE4o/s1600/example.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The present problem formulation with the newly added past present rules.</td></tr>
</tbody></table>
<div class="MsoNormal">
</div>
</div>
</div>
<span lang="EN-US" style="mso-ansi-language: EN-US;">The source code for the respective Eclipse plugin is public available and can be obtained from <a href="http://code.google.com/p/code-candies/source/">http://code.google.com/p/code-candies/source/</a></span>. Feel free to explore the tool with you own Christmas present problems.<br />
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
For me the tool works just fine :)</div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;"><br /></span></div>
<div class="MsoNormal">
<span lang="EN-US" style="mso-ansi-language: EN-US;">[1]
Wikipedia: Linear Programming. <a href="http://en.wikipedia.org/wiki/Linear_programming">http://en.wikipedia.org/wiki/Linear_programming</a><br />
[2] Sourceforge: LPSolve IDE. <a href="https://sourceforge.net/projects/lpsolve/files/lpsolve/">https://sourceforge.net/projects/lpsolve/files/lpsolve/</a><br />
[3] EMFText. <a href="http://www.emftext.org/">http://www.emftext.org/</a></span></div>
</div>
</div>
</div>
dblcdbluhttp://www.blogger.com/profile/00454452258805862472noreply@blogger.com0tag:blogger.com,1999:blog-8376156611530179869.post-51345049573500746102012-10-18T08:46:00.000-07:002012-11-01T09:12:55.493-07:00Petri-Net Taxonomy Reasoner<div style="text-align: justify;">
Petri nets (and Hierarchical Colored Petri nets [1] (HCPNs) in particular) are
mathematically well-formed
models which are based on an <i>executable</i> formalism. My tool of choice for working on HCPNs is "CPN Tools" [2].<br />
However, you may even represent <i>knowledge</i> in HCPNs in forms of flattened graphs. I'll show you how a relatively simple taxonomy, which (in this case) is actually nothing more than a directed acyclic graph (DAG), is transformed into a data structure usable by the CPN ML language used in HCPNs to define color sets (data types), functions, and so on.<br />
This allows us to create <i>reasoners</i> with which we can either learn additional things (add nodes to the taxonomy graph) or answer queries on this knowledge (i.e. actually applying some graph-algorithm and compute (parts of) the transitive closure or just single paths).<br />
<br />
But enough chitchat for now, let's get down to business. In the following picture you can see the simple example taxonomy:<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-d2TKYvvlcocAheSsGiyC0X8anB9KmX5XHUpVBv8yhJvD2LZXqQbnJq8a1P8pC7H9s33JV9rBhdEna44qPAep7c1F_4UiWQi9c5YKLnT1ndqKEG2xUndX_lrcdpPKA_Sa5_QiKisnuCnJ/s1600/ontology_test_small.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg-d2TKYvvlcocAheSsGiyC0X8anB9KmX5XHUpVBv8yhJvD2LZXqQbnJq8a1P8pC7H9s33JV9rBhdEna44qPAep7c1F_4UiWQi9c5YKLnT1ndqKEG2xUndX_lrcdpPKA_Sa5_QiKisnuCnJ/s320/ontology_test_small.png" width="303" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A simple taxonomy as a DAG created using yEd [3]</td></tr>
</tbody></table>
<br />
<br />
As you might see, the Is-A relationships are in reverse direction (the automatic layout of yEd would not allow the "correct" direction) but this is just a cosmetic issue. Anyways, what you can see is, that we defined the concepts (or classes) "Thing", "Animal", etc. and what it means is that "an animal is a thing" and so on (again, intention is reverse to edges' direction...). This is quite like a class inheritance tree as it is common to software technologists.<br />
<br />
A short recall: we'd like to use such a graph as knowledge in an HCPN in order to reason about this knowledge.<br />
<br />
<strike>CPN ML (a variant of SML/NJ) does not support hierarchical data structures (compare to the composite design pattern).</strike> [Edit:] Actually, CPN ML and SML/NJ DO support datatypes, which are inherently recursive. However, they cannot be used as colors in an HCPN, so this is out of the question [Thanks and credits to <a href="http://westergaard.eu/" rel="nofollow" target="_blank">Michael Westergaard</a>].<br />
Thus, we must flatten this taxonomy graph into a list so that we can process it (feel free to tell me when there's a better solution).<br />
I therefor wrote an eclipse plug-in with which you can comfortably do the conversion between a yEd's graphml file and an appropriate
CPN ML
list-style graph representation, which looks like:<br />
<br />
<blockquote align="justify" class="tr_bq" style="background-color: #dddddd;">
<span style="font-family: "Courier New", Courier, monospace;">
val initial_knowledge = [<br />{p="",c="Thing",a=[]}<br />,{p="Thing",c="Plant",a=[]}<br />,{p="Plant",c="Tree",a=[]}<br />,{p="Thing",c="Animal",a=[]}<br />,{p="Animal",c="Mammal",a=[]}<br />,{p="Mammal",c="Human",a=[]}<br />,{p="Human",c="Nicholas",a=[]}<br />,{p="Human",c="Sebastian",a=[]}<br />,{p="Human",c="Anthony",a=[]}<br />,{p="Thing",c="Robot",a=[]}<br />,{p="Robot",c="NAO",a=[]}<br />]
</span></blockquote>
<br />
<br />
<span style="font-family: "Courier New", Courier, monospace;"><b>initial_knowledge</b></span> is the list variable, <span style="font-family: "Courier New", Courier, monospace;"><b>p</b></span> is the parent node, <span style="font-family: "Courier New", Courier, monospace;"><b>c</b></span> is the actual node (i called it child...) and<span style="font-family: "Courier New", Courier, monospace;"><b>a</b></span> is a list of attributes (key/value pairs).<br />
<br />
Now let's see the Petri net (I'll post a link later under which you can find the plug-in and net)...<br />
<br />
<i><u>Please note:</u> wherever there's "ontology" in the nets, replace it with "knowledge"...</i><br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0NZpaMAx09GlX3nJ3_YzCXpBwYGOlPqHe-Pu4qAv9OYUA_EsEAqmhAw-HYqCsEPrnKVP4w73GMQm4RInhya0vgMxb5Aj54zTMvw5qTS-8E14Nd0lCNiOYdC4MglpjwgZQv1AhrsA1D7Ya/s1600/ontology_reasoner_page_0.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="298" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0NZpaMAx09GlX3nJ3_YzCXpBwYGOlPqHe-Pu4qAv9OYUA_EsEAqmhAw-HYqCsEPrnKVP4w73GMQm4RInhya0vgMxb5Aj54zTMvw5qTS-8E14Nd0lCNiOYdC4MglpjwgZQv1AhrsA1D7Ya/s640/ontology_reasoner_page_0.jpg" width="640" /></a><br />
<br />
In the middle bottom there is the large green rectangle which shows the (initial) knowledge, while in the top left there are three "queries" on this knowledge, which we can interpret as<br />
<br />
1) is Anthony a Mammal?<br />
2) is NAO a Robot?<br />
3) is Sebastian a Robot?<br />
<br />
And let's see what happens when we fire the transitions:<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiDtDTSZrsimcxpmd684sLq2xnZ_dWDjbiyESwNtJkyw2gAWij-8vtMU09TC_cwiJWniu3pQrfvQmwZbOS8OLDx1fRW0H1zP7ReKwn5zOXcOoI25Fo0i68I0omMaDmf25mIHVe2gl9CSpO/s1600/ontology_reasoner_page_1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="298" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiDtDTSZrsimcxpmd684sLq2xnZ_dWDjbiyESwNtJkyw2gAWij-8vtMU09TC_cwiJWniu3pQrfvQmwZbOS8OLDx1fRW0H1zP7ReKwn5zOXcOoI25Fo0i68I0omMaDmf25mIHVe2gl9CSpO/s640/ontology_reasoner_page_1.jpg" width="640" /></a><br />
<br />
The transition chose query 2 and it is about to be answered...<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEYulvo_OniIyASiP8hQWF4Bxn-dIzRU7UDMXWIOzW84TcUfl1kHJLO83B4csRAncmNjdGbMXKXJTwVp8zIyquM5q1bYqYo63xx-baNYUsV5w52zxTRy5x65NTZprooTuHjugKBcZpPKgw/s1600/ontology_reasoner_page_4.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="278" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEYulvo_OniIyASiP8hQWF4Bxn-dIzRU7UDMXWIOzW84TcUfl1kHJLO83B4csRAncmNjdGbMXKXJTwVp8zIyquM5q1bYqYo63xx-baNYUsV5w52zxTRy5x65NTZprooTuHjugKBcZpPKgw/s640/ontology_reasoner_page_4.jpg" width="640" /></a><br />
<br />
When place "Accepted?" receives the query token (instead of an "empty" token) then this query was accepted, which can be interpreted as "the assertion is true".<br />
Accordingly, query 3 should result in an "empty" token, since "Sebastian" is not a "Robot" in our knowledge (we skipped query 1 here, which is also accepted):<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghczFJGnRzwuTFpu87Oy8mEhpWlaTWZH4ODxDge9NZOcH-ft5dVIwV8ecThxPg_2gp9dp9Z5HWqsTkL-SAsIuDEZj1twU1j9hkYKr6HpyIX1s7U8apPBfnpiukjJmTcY3DhbdmOVSxAziF/s1600/ontology_reasoner_page_5.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="326" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEghczFJGnRzwuTFpu87Oy8mEhpWlaTWZH4ODxDge9NZOcH-ft5dVIwV8ecThxPg_2gp9dp9Z5HWqsTkL-SAsIuDEZj1twU1j9hkYKr6HpyIX1s7U8apPBfnpiukjJmTcY3DhbdmOVSxAziF/s640/ontology_reasoner_page_5.jpg" width="640" /></a><br />
<br />
And the result:<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBWzVQbQ7qb5JGeYq-ozOCJZS72t-vM7ipUO_JpwNkq9Yr9GqlWnZxW1NoMgy_VbPseLVzfY1LKNaGp2dxmkjbtCJo0FZwMa_DVRkXc-y4whg7ngS28W-W7Fmab6O7I37W6AOjLpm_-hao/s1600/ontology_reasoner_page_6.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="326" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBWzVQbQ7qb5JGeYq-ozOCJZS72t-vM7ipUO_JpwNkq9Yr9GqlWnZxW1NoMgy_VbPseLVzfY1LKNaGp2dxmkjbtCJo0FZwMa_DVRkXc-y4whg7ngS28W-W7Fmab6O7I37W6AOjLpm_-hao/s640/ontology_reasoner_page_6.jpg" width="640" /></a><br />
<br />
Finally, let's have a look at the function which does all the work: <span style="font-family: "Courier New", Courier, monospace;"><b>accept ( ruleTest, ont )</b></span>:<br />
<br />
<blockquote align="justify" class="tr_bq" style="background-color: #dddddd;">
<span style="font-family: "Courier New", Courier, monospace;">
fun accept ( rt:RuleTest, []:Knowledge ) : BOOL<br />
= true<br />| accept ( rt:RuleTest, know:Knowledge ) : BOOL<br />
= testRule(#r rt, hd know) orelse runFold(rt, know);
</span></blockquote>
<br />
<br />
As a shorthand, when we have no knowledge (empty list) just accept the RuleTest. Otherwise, look whether the searched pair is the root itself (another shorthand) or, otherwise, call runFold, which is explained further down.<br />
<br />
The color sets used are:<br />
<br />
<blockquote align="justify" class="tr_bq" style="background-color: #dddddd;">
<span style="font-family: "Courier New", Courier, monospace;">
colset ATTR_VAL = record k:STRING * v:STRING;<br />
colset ATTR_LIST = list ATTR_VAL;<br />
colset Rule = record p:STRING * c:STRING * a:ATTR_LIST;<br />
colset Knowledge = list Rule;<br />
colset RuleTest = record r:Rule * id:INT;
</span></blockquote>
<br />
<br />
A <span style="font-family: "Courier New", Courier, monospace;"><b>Rule</b></span> is actually a node in our flattened/serialized tree which knows about its parent's name (<span style="font-family: "Courier New", Courier, monospace;"><b>p</b></span>) its own name (<span style="font-family: "Courier New", Courier, monospace;"><b>c</b></span>) and has a list of attributes (<span style="font-family: "Courier New", Courier, monospace;"><b>a</b></span>), whereas each attribute is a key/value pair. The attributes denote further knowledge about the node itself and could be used to store attributes of the edge (relationship) between the node and its parent, but, of course, you could also extend colorset <span style="font-family: "Courier New", Courier, monospace;"><b>Rule</b></span> to have a second attribute list (to clearly separate the node's and the edge's attributes).<br />
<br />
Variables (denoted by <span style="font-family: "Courier New", Courier, monospace;"><b>var</b></span>) and the constant (denoted by <span style="font-family: "Courier New", Courier, monospace;"><b>val</b></span>):
<br />
<blockquote align="justify" class="tr_bq" style="background-color: #dddddd;">
<span style="font-family: "Courier New", Courier, monospace;">
var rule,rule1,rule2,toLearn : Rule;<br />
val emptyRule = {p="",c="",a=[]};<br />
var ruleTest : RuleTest;<br />
var parent,child,key,value,p1,c1 : STRING;<br />
var id : INT;<br />
var ont : Ontology;
</span></blockquote>
<br />
<br />
Here's not much to say, except that we use <span style="font-family: "Courier New", Courier, monospace;"><b>emptyRule</b></span>as the constant for differentiating between an accepted and a rejected rule test/query.<br />
<br />
The other functions needed:<br />
<br />
<blockquote align="justify" class="tr_bq" style="background-color: #dddddd;">
<span style="font-family: "Courier New", Courier, monospace;">
fun runFold ( rt:RuleTest, know : Knowledge ) : BOOL<br />
= #found (foldr foldRule {r=(#r rt),found=false} know);<br />
<br />
fun foldRule ( rule:Rule, test:FoldRuleInput ) : FoldRuleInput<br />
= if ((#found test) orelse (#c rule <> #c (#r test)))<br />
then test <span style="background-color: #b6d7a8;">(*search finished or continue search*)</span><br />
else (if (#p rule = #p (#r test))<br />
then {r=(#r test),found=true} <span style="background-color: #b6d7a8;">(*found*)</span><br />
else {r={p=(#p(#r test)),c=(#p know),a=(#a(#r test))},found=false} <span style="background-color: #b6d7a8;">(*traverse upwards*)</span><br />
);
</span></blockquote>
<br />
<br />
So, here we have <span style="font-family: "Courier New", Courier, monospace;"><b>runFold</b></span> which I introduced earlier. What this function actually does is traversing the serialized tree bottom-up (from leaf to root). Therefor it uses the SML function <span style="font-family: "Courier New", Courier, monospace;"><b>foldr</b></span> and you could use <span style="font-family: "Courier New", Courier, monospace;"><b>foldl</b></span> to go top-down.<br />
<br />
I'll leave the rest to you and look forward to your comments, questions, and suggestions.<br />
<br />
You find the sources under: <a href="http://code.google.com/p/code-candies/source/">http://code.google.com/p/code-candies/source/</a><br />
Search the trunk for "HCPN-Taxonomy-Reasoner".<br />
<br />
[1] {Jensen, Kurt and Kristensen, Lars M.} {Coloured Petri Nets} {2009}<br />
[2] <a href="http://cpntools.org/" target="_blank">http://cpntools.org/</a><br />
[3] <a href="http://www.yworks.com/de/products_yed_about.html" target="_blank">http://www.yworks.com/de/products_yed_about.html</a></div>
Unknownnoreply@blogger.com0