### Decision Management Community November 2014 Challenge: Who killed Agatha?

From DM Community Challenge Nov-2014:

A model for this problem is actually one of the first I implement whenever I learn a new Constraint Programming (CP) system since in my approach it has some features that are important to test (they are explained in some details below):Someone in Dreadsbury Mansion killed Aunt Agatha.

Agatha, the butler, and Charles live in Dreadsbury Mansion, and

are the only ones to live there. A killer always hates, and is

no richer than his victim. Charles hates noone that Agatha hates.

Agatha hates everybody except the butler. The butler hates everyone

not richer than Aunt Agatha. The butler hates everyone whom Agatha hates.

Noone hates everyone. Who killed Agatha?

- reification: "reasoning about constraints"
- matrix element: how to index a matrix with decision variables

All the decodings has the same approach: defining two binary 3x3 matrices of decision variables:

- a "hates" matrix, i.e. who hates who
- a "richer" than matrix: who is richer than who

`Killer`

decision variable of range 1..3 (Agatha=1, Butler=2,
and Charles=3). In some encodings (as the one below), `Victim`

is also
a decision variable, but we know that Agatha is the Victim from the
start so this decision variable can be skipped.
The constraints will then on these two decision variables, the two matrices + the

`Killer`

decision variable.
First I describe the MiniZinc model in detail and after that a discussion about the solution and why it returns 8 solutions (all with the same killer: Agatha).

## The Minizinc model

My original MiniZinc model is here who_killed_agatha.mzn.The decoding shown below is slightly altered for simpler presentation.

### Initiation of constants and domains

The following defines the dimension of the matrices (3x3) and also the domain - the possible values - of the killer and victim variables (1..3).int: n = 3; set of int: r = 1..3;Here we define the constants

`agatha`

, `butler`

, and `charles`

.
The values are fixed to
the integers 1..3 since the solvers used handles finite domains in terms
of integers. (There are exceptions to this. To state it short: finite domains
in terms of integers is the most common in CP. Some systems also support set variables
and/or float decision variables.)
% the people involved int: agatha = 1; int: butler = 2; int: charles = 3;

### Decision variables

The two decision variables`the_killer`

and `the_victim`

has both the domain
1..3, i.e. the set {agatha, butler charles}.
var r: the_killer; var r: the_victim;The 3x3 entries in the two matrices

`hates`

and `richer`

are binary decision
variables: 1 represents true, 0 represents false.
array[r,r] of var 0..1: hates; array[r,r] of var 0..1: richer;The following statement just states that the CP solver should use its default search method.

solve satisfy;

*Aside: There is a range of different search heuristics available for most CP solvers, than can speed up more complex CSP's significantly, e.g. for an array*

`x`

of decision variables one could state:
solve :: int_search(x, first_fail, indomain_split, complete);but for this simple problem we just settle for the default.

### Constraints

Next is the constraint section where all the requirements (constraints) of the problem are specified. The order of the constraints is the same order as the problem description. In contrast to the MiniZinc version on my MiniZinc site (the link above), I have here separated each constraint in its own section to emphasize the specific constraint.### Constraint: A killer always hates, and is no richer than his victim.

Here we see an example of a "matrix element" constraint, i.e. that a decision variable (`the_killer`

) is used as an index of a matrix of decision variables,
e.g.
hates[the_killer, the_victim] = 1<[Aside: In MiniZinc this can be done in this most syntactical pleasing ("natural") way, though most of the other CP systems cannot handle this syntax so an alternative syntax must be used. However, most CP systems have a syntax for the one dimensional element constraint, which is then stated as

element(Y,X,Z)which corresponds to

X[Y] = Z,where X and both Y and Z can be decision variables. The element constraint is central for CP and is one of the features that separates it from traditional LP/MIP modeling systems.] The first constraint

hates[the_killer, the_victim] = 1simply means that the killer hates the victim, and the second that the killer is not richer than the victim.

constraint % A killer always hates, and is no richer than his victim. hates[the_killer, the_victim] = 1 /\ richer[the_killer, the_victim] = 0 ;

### The concept of richer

The only relations we are using here are hates and richer, and we must take care of the meaning of these concepts.**Hates**: Regarding the concept of hatred there is no logic involved how it can be used: A and B can both hate each other, or one of them can hate the other, or neither hates the other. Note that A can hate him/herself.

**Richer**: The concept of richer is a completely different matter, however. There is a logic involved in this relation:

- if A is richer than B, then B cannot be richer than A
- A cannot be richer than him/herself

As mentioned above, we don't need to - and cannot - do a similar analysis on (the semantic meaning of) the hate relation.

See below

**A note on the richer relation**for a comment on the assumption that either A is richer than B or B is richer than A.

constraint % define the concept of richer % no one is richer than him-/herself forall(i in r) ( richer[i,i] = 0 ) % (contd...) if i is richer than j then j is not richer than i /\ forall(i, j in r where i != j) ( richer[i,j] = 1 <-> richer[j,i] = 0 ) ;

### Constraint: Charles hates noone that Agatha hates.

Here again, reifications is handy. In pseudo code:FOR EACH person I in the house: IF Agatha hates I THEN Charles don't hate I

constraint % Charles hates noone that Agatha hates. forall(i in r) ( hates[charles, i] = 0 <- hates[agatha, i] = 1 ) ;

### Constraint: Agatha hates everybody except the butler

Here we simply state three hate facts.It is important to not forget that Agatha can hate herself. Missing this fact in this model would yield that either Agatha or Charles is the killer.

constraint % Agatha hates everybody except the butler. hates[agatha, charles] = 1 /\ hates[agatha, agatha] = 1 /\ hates[agatha, butler] = 0 ;

### Constraint: The butler hates everyone not richer than Aunt Agatha.

Same as above, we use reification to handle this:FOR EACH person I in the house IF I is not richer than Agatha THEN Butler hates Iwhich is implemented as

constraint % The butler hates everyone not richer than Aunt Agatha. forall(i in r) ( hates[butler, i] = 1 <- richer[i, agatha] = 0 ) ;

### Constraint: The butler hates everyone whom Agatha hates.

Same reasoning with reifications as above.constraint % The butler hates everyone whom Agatha hates. forall(i in r) ( hates[butler, i] = 1 <- hates[agatha, i] = 1 ) ;

### Constraint: Noone hates everyone.

Here we count - for each person - the number of 1's (i.e. true) for each row in the hates matrix, and ensure that they are less than 3 (i.e. not all).constraint % Noone hates everyone. forall(i in r) ( sum(j in r) (hates[i,j]) <= 2 ) ;

### Who killed Agatha?

As mentioned above, this is not really needed since we could have hard coded`the_victim`

to `agatha`

without changing anything.
constraint % Who killed Agatha? the_victim = agatha ;To summarize: This model use a couple of important concepts in Constraint Programming:

- decision variables with specific (finite) domains
- reifications, implication and equivalence between constraints
- element constraint (here in term of the more complex variant: matrix element)

## Solution and analysis

There are total 8 different solutions for this MiniZinc model, all stating that Agatha is the killer. (Being able to get all solutions to a combinatorial problem is a excellent feature in Constraint Programming.)The reason this model give more than one solution is because it is - in my interpretation of the problem - under constrained: there is not enough information about certain relations in the

`hates`

and `richer`

matrices to yield a unique solution.
Below are the values of the

`hates`

and `richer`

matrices after all constraints have
been activated, but before search (searching in the search tree and assign all the decision
variables to give a solution), as well as the killer variable.
The entries with "0..1" are the decision variables that are not constrained (decided) enough before search. (Note: Not all CP solvers have the feature to show the inferred variable domains before search. The table below is from my Picat model, slightly altered: who_killed_agatha.pi)

Killer: killer= 1 Hates -------- Agatha : Agatha : 1 Butler : 0 Charles: 1 Butler : Agatha : 1 Butler : 0 Charles: 1 Charles: Agatha : 0 Butler : 0..1 Charles: 0 Richer -------- Agatha : Agatha : 0 Butler : 0 Charles: 0..1 Butler : Agatha : 1 Butler : 0 Charles: 0..1 Charles: Agatha : 0..1 Butler : 0..1 Charles: 0These undecided variables involves if:

- Charles hates Butler (or not)
- Agatha is richer than Charles (or not)
- Butler is richer than Charles (or not)
- Charles is richer than Agatha (or not)
- Charles is richer than Butler (or not)

- The killer has been assigned to 1 (= Agatha).
- Many (namely 5) of the variables including Charles are undecided before search, i.e. using the constraints only can not figure out if they are true of not. This is perhaps not too surprising since most constraints in the model - and problem statement - involves only Agatha and Butler.

- "Agatha is richer than Charles" and "Charles is richer than Agatha"
- "Butler is richer than Charles" and "Charles is richer than Butler"

Thus 8 different solutions:

[0,1,0,1,0] [0,1,0,1,1] [0,1,1,0,0] [0,1,1,0,1] [1,0,0,1,0] [1,0,0,1,1] [1,0,1,0,0] [1,0,1,0,1]This concludes the analysis.

## A note on the "richer" relation

Nothing rules out that A can be as rich as B (i.e. that neither is richer than the other). However, in this simple model, we assume a stricter variant: that either A is richer than B, or B is richer than A. If we would change the equivalence relationricher[i,j] <-> richer[j,i] = 0(which means:

IF A is richer than B THEN B is not richer than A AND IF B is not richer than A THEN A is richer than B)to an implication

richer[i,j] -> richer[j,i] = 0

(IF A is richer than B THEN B is not richer than A)then it don't change the principal solution but we would yield 18 solutions instead of 8, all point to the same killer: Agatha.

## OTHER ENCODINGS

Here is a list of all the encodings of the Agatha murder problem that I have implemented so far. Whenever I learn a new CP system, the Agatha problem will probably be one of the first to test. See http://hakank.org/common_cp_models/#whokilledagatha:- AIMMS+CP: WhoKilledAgatha.aim
- AMPL: who_killed_agatha.mod
- B-Prolog: who_killed_agatha.pl
- Choco: WhoKilledAgatha.java
- Choco3: WhoKilledAgatha.java
- Comet: who_killed_agatha.co
- ECLiPSE: who_killed_agatha.ecl
- Essence'/Savile row: who_killed_agatha.eprime
- Essence'/Tailor: who_killed_agatha.eprime
- Gecode: who_killed_agatha.cpp
- Google CP Solver/C#: who_killed_agatha.cs
- Google CP Solver/Java: WhoKilledAgatha.java
- Google CP Solver/Python: who_killed_agatha.py
- JaCoP: WhoKilledAgatha.java
- JaCoP/Scala: WhoKilledAgatha.scala
- JSR-331: WhoKilledAgatha.java
- MiniZinc: who_killed_agatha.mzn
- OscaR: WhoKilledAgatha.scala
- Picat: who_killed_agatha.pi
- SICStus: who_killed_agatha.pl
- Zinc: who_killed_agatha.zinc
- Answer Set Programming: who_killed_agatha.lp Note: Answer Set Programming is not a CP system but is interesting to see the encoding as a comparison.