In my role as the Director of Analytics, I enjoy working with the Arkieva team and our clients, in building optimization models which help organizations make intelligent decisions with regards to meeting demand, capacity allocation, inventory levels, factory schedules, forecasting, and cancer research. These models are built using a variety of mathematical methods including Boolean or binary which are powerful and well adapted for yes/no, on/off, or success/failure situations where the only permitted values are zero (0) and one (1).
Solving Business Questions with Optimization Models
Binary models are used regularly to help with such questions as:
- Should we make a certain product today? No is represented by zero, yes by the value one.
- What setup should we assign to a resource today?
- Was there any demand for a certain product today?
- Did the patient recover in 5 days or less or more than 5 days?
- Will the resource be available today?
- What are the chances the cancer treatment will be successful?
As well as fun stuff such as solving Sudoku puzzles and solving mysteries!
Who is Guilty in the Land of Alice – only the model knows!
With the November 2017 release of a “Murder on the Orient Express”, I was reminded of the following detective puzzle and the use of “Boolean or Binary (0/1) models” to solve the mystery.
The Puzzle
The following logic puzzle is adapted from Raymond Smullyan’s book “Alice in Puzzle-Land”. The jam had been stolen and the three suspects are the March Hare, the Mad Hatter, and the Dormouse. It is possible none of them stole the jam or any combination of them (including all three) has stolen the jam.
They were arrested and each made one statement.
- The March Hare: I am not guilty.
- The Mad Hatter: I am not guilty.
- The Dormouse: At least one of the others speaks the truth.
Further investigation produced the following conclusions (facts known to be true).
- Only one of the suspects is guilty
- The March Hare and the Dormouse didn’t both tell the truth.
With this information, the challenge is to determine who is guilty, who is not guilty, or that we lack sufficient information to make a clear determination. We will first outline the process without the explicit use of binary computations and then demonstrate this powerful computational approach.
The Solution Process
Step 1: identify all possible solutions.
In “math-speak” this is a “state-space”. Table 1 shows the 8 possible solutions ranging from all of them are not guilty (option 1) to all of them are guilty (option 8). There is one row for each option and one column for each character, where the value in the cell is the “guilt status” of this character in this option. A character can be “not guilty” (0) or guilty (1). The last column, option status, indicates whether, given the information available, this option is still possible (1) or has been moved to “not possible” (0). For now, all 8 options are possible.
Our goal is to use the clues to move as many options as we can from the “possible state (1)” to the “not possible state (0)”. If, after using all the information from our clues, we can have only one option left as possible (1) – then we will know which characters stole the jam and have solved the mystery.
Step 2: Using Fact 1 to move options from possible to not possible
Fact 1 states exactly one suspect is guilty. How can we use the information to eliminate as many options as possible? Only an option (row) with one value of “guilty” fits this fact. These options are 2, 3, and 5 as indicated in Table 2. Options 1, 4, 6, 7, and 8 are now classified as not possible.
Step 3: Using Fact 2 to move options from possible to not possible – a tad more complicated
Fact 2 states the March Hare and Dormouse didn’t both tell the truth – this fact is met when
- The March Hare has stated the truth and Dormouse has lied
- The March Hare has lied and the Dormouse has stated the truth
- The March Hare has lied and the Dormouse has lied
What is not possible is the fourth combination
- The March Hare has stated the truth and the Dormouse has started the truth
Therefore any combination which makes the statement of the March Hare true and the statement of the Dormouse true is eliminated. Table 3 summarizes this result
Our next task is to determine which options make the March Hare statement true and which options make the Dormouse statement true!
Which options make the March Hare statement true? The March Hare stated he is not guilty, therefore any option where the March Hare is not guilty makes his statement true and any option where he is guilty makes his statement false. Column 5 in Table 4 classifies each option.
- March Hare statement true – options 1, 2, 3, and 4 – value in March Hare column “not guilty”
- March Hare statement false – options 5, 6, 7, and 8 – value in March Hare column is guilty
Which options make the Dormouse statement true? The Dormouse stated, “at least one of the others speaks the truth.” The others are the March Hare and the Mad Hatter. Each stated he was not guilty. Therefore any option where the March Hare is not guilty, the Mad Hatter is not guilty or both not guilty makes the Dormouse statement true. However, if both are guilty, then the Dormouse statement is false. Column 6 in Table 4 classifies each option.
- Dormouse statement true – options 1, 2, 3, 4, 5, and 6
- Dormouse statement false – options 7 and 8 – the value in the March Hare column and the Mad Hatter Column for these options is guilty.
Applying Fact 2 to move options from possible to not possible – Any option where the statement by the March Hare and Dormouse are both true is not permitted based on Fact 2. Therefore options 1, 2, 3, and 4 moves from possible to not possible. Options 5, 6, 7, and 8 remain possible. Table 4 column 7 summarizes this information.
Step 4: Combining Information from Fact 1 and Fact 2 to Solve the Mystery
For an option to be a candidate for who is guilty, it must be possible under Fact 1 and Fact 2.
- Table 2 identifies 2, 3, and 5 are possible based on Fact 1
- Table 4 identifies 5, 6, 7, and 8 are possible based on Fact 2
The only option in the possible list for Fact 1 and possible list for Fact 2 is option 5. Option 5 has March Hare guilty and the other two characters not guilty. The mystery is solved – the March Hare stole the jam and acted alone.
The Binary / Boolean Computational Model
Mathematical models much prefer numbers over characters. A favorite approach to problems like our mystery where there are two possible states for a value (true/false, not guilty/guilty, possible/not possible) is the use of the values 0 and 1 – referred to as Boolean or Binary. Below we outline the use of this computational model approach to our puzzle below.
Step 1: Convert Table 1 to a Binary Table
Table 5 has the same information at Table 1 but in binary form. For the character columns “0” is not guilty and “1” is guilty. For the option status column, “0” is not possible, 1 is possible
Step 2: Using Fact 1 to move options from possible to not possible
Fact 1 states exactly one suspect is guilty. Computationally this can be expressed as – where the sum of each row over the three characters is 1, then this option is possible (1). If not this option is not possible (0). Table 6 has these computations. There is value of 1 in the option status column for options 2, 3, and 5. In Table 2, these same options have the value “possible”.
Step 3: Using Fact 2 to move options from possible to not possible – a tad more complicated
Fact 2 states the March Hare and the Dormouse didn’t both tell the truth. This eliminates any option where the March Hare and Dormouse are both telling the truth.
Which options make the March Hare statement true? The March Hare stated he is not guilty. Any option where the value in the March Hare cell is 0 is an option where the March Hare has told the truth. These are options 1, 2, 3, and 4. Table 7 column 5 has this computation; the value of 1 indicates for this option the March Hare is telling the truth.
Which options make the Dormouse statement true? Any option where the March Hare and Mad Hatter are both guilty (1) makes the Dormouse statement not true. If we apply, the logical operator “and” (˄) between the March Hare column and the Mad Hatter column, any option where we get a 0 is an option where the Dormouse is telling the truth. Columns 6 and 7 of Table 7 show these computations. A value of 1 in column 7 indicates this option has the Dormouse telling the truth, a zero the Dormouse is not telling the truth.
Applying Fact 2 to move options from possible to not possible- Any option where the statement by the March Hare and Dormouse are both true (value 1) is not permitted based on Fact 2. If column 5 is 1 and column 7 is then the value is column 8 is 0. Computationally an option remains possible when 0= (col_5 ˄col_7). Column 8 shows options still possible (value of 1) these are options 5, 6, 7, and 8.
Step 4: Combining Information from Fact 1 and Fact 2 to Solve the Mystery
For an option to be a candidate for who is guilty, it must be possible under Fact 1 and Fact 2. If we apply the logical operation and (^) between the last column of Table 6 (0 1 1 0 1 0 0 0) and the last column of Table 7 (0 0 0 0 1 1 1 1), then we get (0 0 0 0 1 0 0 0). The single 1 in the fifth position tells us this is the only option that is possible for Fact 1 and Fact 2. This is the computational method to determine which options are possible for both facts.
Summarizing the computation
The following computational steps from the 1992 paper, Solving Two-State Logic Problems with Boolean Arrays by IBM language experts Dr. Manual Alfonseca and Dr. James Brown summarizes the binary computational solution in a powerful notation and programing language APL during the first Artificial Intelligence wave.
HARE ß 0 0 0 0 1 1 1 1
The symbol “ß” means assign the value to this variable
HAT ß 0 0 1 1 0 0 1 1
DOR ß 0 1 0 1 0 1 0 1
The three variables HARE, HAT, and DOR have the values in Table 5, columns 2, 3, and 4.
FACT1ß 1 = (HARE + HAT + DOR)
FACT1 now has the values 0 1 1 0 1 0 0 0 – Table 6 last column
FACT2 ß 0 = ((0=HARE) ˄ (0=(HARE˄HAT)))-
FACT2 has the values 0 0 0 0 1 1 1 1 – Table 7 last column
SOLULTION ß FACT1˄FACT2
SOLITION has the values 0 0 0 0 1 0 0 0. The “1” in the fifth position tells us option 5 is the solution – the Hare is guilty.
The Takeaway
Binary methods involve computations, where the only values permitted, are zero and one. These powerful methods support the development of very helpful models that capture a diverse set of real world situations where the option is yes/no, on/off, success/failure … as well as solving fun puzzles.
Enjoyed this post? Subscribe or follow Arkieva on Linkedin, Twitter, and Facebook for blog updates.
