Do Christmas Present Decisions based on ILPs

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. 

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:

1. First, each person should get exactly one gift.
2. 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.
3. 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.

A simple example for a family consisting of six members.

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

• Husband 1 buys a present for Aunt 2
• Aunt 1 buys a present for Child 2
• Child 1 buys a present for Husband 2
• Husband 2 buys a present for Aunt 1
• Aunt 2 buys a present for Child 1
• Child 2 buys a present for Husband 1

The constraints include:

• No present from Husband 1 for Aunt 1
• No present from Husband 1 for Child 1
• No present from Aunt 1 for Child 1
• No present from Aunt 1 for Aunt 2
• …

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!

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.

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 a and b for which we want to compute integer values). Second, we define an objective function (e.g., we can say that the sum of a and b should be as small as possible). Third, we can define some constraints (e.g. that a is b-2 and b is 2*a). Afterwards, an ILP solver will compute an optimal solution for our ILP. In our example the optimal solution will be a=2 and b=4.

So how does an ILP solution for our example looks like?

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 0 or 1 indicating a non-drawn or drawn combination. Thus, we need the following variables: 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.

Next, we have to specify our constraints. First, each person has to buy exactly one present: For example, the constraint husband1_aunt2 + husband1_husband2 + husband1_child2 = 1 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: aunt2_husband1 + husband2_husband1 + husband2_child2 = 1.

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: cost_husband1 = 2 child2_husband1 + aunt2_husband1.

Finally, we have to specify our objective function which is simply to minimize the cost of former presents: min cost_aunt1 + cost_husband1 + cost_child1 + cost_aunt2 + cost_husband2 + cost_child2.

And we are done. Our whole program looks as shown below (if we consider no former presents):

/* Objective function */

min: cost_Aunt1 + cost_Husband1 + cost_Child1 + cost_Aunt2 + cost_Husband2 + cost_Child2;

/* Constraints */

/* One customer per guy. */

Aunt1_Husband2 + Aunt1_Child2 = 1;

Husband1_Aunt2 + Husband1_Husband2 + Husband1_Child2 = 1;

Child1_Aunt2 + Child1_Husband2 + Child1_Child2 = 1;

Aunt2_Husband1 + Aunt2_Child1 = 1;

Husband2_Aunt1 + Husband2_Husband1 + Husband2_Child1 = 1;

Child2_Aunt1 + Child2_Husband1 + Child2_Child1 = 1;

/* One present per guy. */

Husband2_Aunt1 + Child2_Aunt1 = 1;

Aunt2_Husband1 + Husband2_Husband1 + Child2_Husband1 = 1;

Aunt2_Child1 + Husband2_Child1 + Child2_Child1 = 1;

Husband1_Aunt2 + Child1_Aunt2 = 1;

Aunt1_Husband2 + Husband1_Husband2 + Child1_Husband2 = 1;

Aunt1_Child2 + Husband1_Child2 + Child1_Child2 = 1;

/* Cost per customer. */

cost_Aunt1 = 0;

cost_Husband1 = 0;

cost_Child1 = 0;

cost_Aunt2 = 0;

cost_Husband2 = 0;

cost_Child2 = 0;

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:

ILP solving result.

Thus:

• Aunt1 buys a present for Child2
• Husband1 buys a present for Husband2
• Child1 buys a present for Aunt2
• Aunt1 buys a present for Child1
• Husband2 buys a present for Husband1
• Child2 buys a present for Aunt1

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:

/* Cost per customer. */
cost_Aunt1 = Aunt1_Child2;
cost_Husband1 = Husband1_Husband2;
cost_Child1 = Child1_Aunt2;
cost_Aunt2 = Aunt2_Child1;
cost_Husband2 = Husband2_Husband1;
cost_Child2 = Child2_Aunt1;

And we get a new valid and optimal combination.

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.

Thus, this year, I implemented a simple DSL using Eclipse and EMFText [3] to formulate the problem in a more elegant way:

Formulation of the present problem in a simple DSL.

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 a conflicts b and b conflicts a have to be defined for undirected exclusions. Finally, past present combinations can be specified.

Afterwards, the Eclipse plugin will generate the respective ILP, triggers the ILP solver and will propagate back the valid solution:

Triggering ILP solving from the DSL.

Result of the ILP solving.

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:

The present problem formulation with the newly added past present rules.

The source code for the respective Eclipse plugin is public available and can be obtained from http://code.google.com/p/code-candies/source/. Feel free to explore the tool with you own Christmas present problems.

For me the tool works just fine :)

[1] Wikipedia: Linear Programming. http://en.wikipedia.org/wiki/Linear_programming
[2] Sourceforge: LPSolve IDE. https://sourceforge.net/projects/lpsolve/files/lpsolve/
[3] EMFText. http://www.emftext.org/

Petri-Net Taxonomy Reasoner

Petri nets (and Hierarchical Colored Petri nets [1] (HCPNs) in particular) are mathematically well-formed models which are based on an executable formalism. My tool of choice for working on HCPNs is "CPN Tools" [2].
However, you may even represent knowledge 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.
This allows us to create reasoners 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).

But enough chitchat for now, let's get down to business. In the following picture you can see the simple example taxonomy:

A simple taxonomy as a DAG created using yEd [3]

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.

A short recall: we'd like to use such a graph as knowledge in an HCPN in order to reason about this knowledge.

CPN ML (a variant of SML/NJ) does not support hierarchical data structures (compare to the composite design pattern). [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 Michael Westergaard].
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).
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:

val initial_knowledge = [
{p="",c="Thing",a=[]}
,{p="Thing",c="Plant",a=[]}
,{p="Plant",c="Tree",a=[]}
,{p="Thing",c="Animal",a=[]}
,{p="Animal",c="Mammal",a=[]}
,{p="Mammal",c="Human",a=[]}
,{p="Human",c="Nicholas",a=[]}
,{p="Human",c="Sebastian",a=[]}
,{p="Human",c="Anthony",a=[]}
,{p="Thing",c="Robot",a=[]}
,{p="Robot",c="NAO",a=[]}
]

initial_knowledge is the list variable, p is the parent node, c is the actual node (i called it child...) anda is a list of attributes (key/value pairs).

Now let's see the Petri net (I'll post a link later under which you can find the plug-in and net)...

Please note: wherever there's "ontology" in the nets, replace it with "knowledge"...



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

1) is Anthony a Mammal?
2) is NAO a Robot?
3) is Sebastian a Robot?

And let's see what happens when we fire the transitions:



The transition chose query 2 and it is about to be answered...



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



And the result:



Finally, let's have a look at the function which does all the work: accept ( ruleTest, ont ):

fun accept ( rt:RuleTest, []:Knowledge ) : BOOL
= true
| accept ( rt:RuleTest, know:Knowledge ) : BOOL
= testRule(#r rt, hd know) orelse runFold(rt, know);

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.

The color sets used are:

colset ATTR_VAL = record k:STRING * v:STRING;
colset ATTR_LIST = list ATTR_VAL;
colset Rule = record p:STRING * c:STRING * a:ATTR_LIST;
colset Knowledge = list Rule;
colset RuleTest = record r:Rule * id:INT;

A Rule is actually a node in our flattened/serialized tree which knows about its parent's name (p) its own name (c) and has a list of attributes (a), 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 Rule to have a second attribute list (to clearly separate the node's and the edge's attributes).

Variables (denoted by var) and the constant (denoted by val):

var rule,rule1,rule2,toLearn : Rule;
val emptyRule = {p="",c="",a=[]};
var ruleTest : RuleTest;
var parent,child,key,value,p1,c1 : STRING;
var id : INT;
var ont : Ontology;

Here's not much to say, except that we use emptyRuleas the constant for differentiating between an accepted and a rejected rule test/query.

The other functions needed:

fun runFold ( rt:RuleTest, know : Knowledge ) : BOOL
= #found (foldr foldRule {r=(#r rt),found=false} know);

fun foldRule ( rule:Rule, test:FoldRuleInput ) : FoldRuleInput
= if ((#found test) orelse (#c rule <> #c (#r test)))
then test (*search finished or continue search*)
else (if (#p rule = #p (#r test))
  then {r=(#r test),found=true} (*found*)
  else {r={p=(#p(#r test)),c=(#p know),a=(#a(#r test))},found=false} (*traverse upwards*)
);

So, here we have runFold 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 foldr and you could use foldl to go top-down.

I'll leave the rest to you and look forward to your comments, questions, and suggestions.

You find the sources under: http://code.google.com/p/code-candies/source/
Search the trunk for "HCPN-Taxonomy-Reasoner".

[1] {Jensen, Kurt and Kristensen, Lars  M.} {Coloured Petri Nets} {2009}
[2] http://cpntools.org/
[3] http://www.yworks.com/de/products_yed_about.html