Rule Solver – Miss Manners

Problem. Miss Manners is throwing a party and being a good host, she wants to arrange good seating. She wants to seat the guests in a boy-girl-boy-girl arrangement so that each guest will have someone on the left or right that has a common hobby. Our decision model needs to help Miss Manners to do it for parties with 16, 32, 64, and 128 guests described in the Excel file that you may download from here.

Implementation. This is a typical constraint satisfaction problem which could be easily represented and resolved by any Constraint Solver. You may find a Java-based solution using OpenRules with Java Solver. While it is very efficient and compact it requires knowledge of Java and hardly could be understood by business analysts. Here is how this problem can be represented and solved using the latest OpenRules Rule Solver.

Problem Definition. Let’s start with the provided test data for the party of 16 guests converted to the OpenRules format in Excel file Test.xls:

Here is the corresponding business Glossary:

Thus, for each Guest we know Name, Gender, and Hobbies. Our goal is to define a Guest’s Seat for all Guests while satisfying Gender and Hobby rules (constraints).

We will assume that seats are numbered from 1 to 16, 32, 64, or 128. The Last Seat is calculated in the above Glossary as a number of elements in the array of Guests.

We will use the following top-level decision “Define” for the problem definition:

For each Guest, we will define the array “Seat Tags” with unique guests tags such as “1 Seat”, “2 Seat”, etc. It can be done using the regular OpenRules decision table:

Here “{{Name of Guest}}” will be opened by OpenRules using the current Guest’s name.

Then we will create the array “Seat Variables” with unknown decision variables for each guest seat that could take values from 1 to Last Seat:

Now we should be able to define all Gender and Hobby rules by posting the proper constraints on these yet unknown decision variables, and then use a standard search strategy to find the proper seats.

First of all, all Seat Variables should take different values from 1 to Last Seat. We also may assume the the first guest is always sitting at the first seat (as all other decision will be simply symmetrical). We may express these constraint in the following table:

To post Gender and Hobby constraints we need to consider all possible pairs of Guests (G1;G2) and state that G1 and G2 should have opposite genders and at least one common hobby. We can do it by executing incompatibility rules for each pair of different guests. We will use the predefined OpenRules “ActionNestedLoops” to iterate over different pairs of guests (G1;G2) inside the array of all “Guests”:

This iteration process will use several intermediate decision variables which we may define in the following temporary glossary:

The decision “IncompatibilityRulesForPairOfGuests” will be executed for each pair of guests (G1;G2) if they have the same Gender (rule 1) or their Hobbies do not intersect (rule 2):

Note that we implemented the above “or” by using two different rules. In both situations we will execute the same Action “DontSeatTogether”:

This action first will define constrained variables for seats on left and right of the Guest1:

Here OpenRules will replace {{Guest1}} and {{Guest2}} with the actual names of Guest1 or Guest2. Then the table “DontSeatTogether” will execute incompatibility constraints such as “Guest2 not Left of Guest1”, “Guest1 at First Seat”, etc. However, we cannot post them unconditionally but rather use them later:

And finally, the action “DontSeatTogether” will post constraint of the type “IfThen” described in the first columns in plain English:

Problem Resolution. We may rely on the predefined search strategy “SolverFindSolution” supported by Rule Solver. We also may print all found values for Seat Variables using the action “SolveLogVariables”:

Main Decision. The will rely on the standard RuleSolver method “DefineAndSolver” to invoke both decisions “Define” and “Solve” as defined by the property “model.goal” in the Environment table:

Here is the automatically generated Decision Diagram:

As you can see, all decision modeling efforts were on problem definition and we don’t have to worry about problem resolution.

Execution Results. Running this decision model produced the following results:

Party of 16 Guests:

Party of 32 Guests:

dave Seat[1] doug Seat[3] jane Seat[2] kate Seat[4] scott Seat[5] sue Seat[6] ann Seat[8] john Seat[7] chuck Seat[9] hope Seat[10] jill Seat[12] dan Seat[11] carol Seat[14] alex Seat[13] pam Seat[16] tim Seat[15]

d Seat[17] e Seat[19] f Seat[18] g Seat[20] h Seat[21] i Seat[22] j Seat[24] k Seat[23] l Seat[25] m Seat[26] n Seat[28] o Seat[27] p Seat[30] q Seat[29] r Seat[32] s Seat[31]

Elapsed time 142.10 milliseconds

Party of 64 Guests:

1 Seat[1] 2 Seat[2] 3 Seat[3] 4 Seat[5] 5 Seat[7] 6 Seat[9] 7 Seat[4] 8 Seat[11] 9 Seat[13] 10 Seat[15] 11 Seat[17] 12 Seat[6] 13 Seat[19] 14 Seat[21] 15 Seat[23] 16 Seat[8] 17 Seat[10] 18 Seat[25] 19 Seat[12] 20 Seat[14] 21 Seat[27] 22 Seat[29]

23 Seat[16] 24 Seat[18] 25 Seat[20] 26 Seat[31] 27 Seat[22] 28 Seat[33] 29 Seat[24] 30 Seat[26] 31 Seat[35] 32 Seat[37] 33 Seat[39] 34 Seat[28] 35 Seat[30] 36 Seat[41] 37 Seat[43] 38 Seat[32] 39 Seat[45] 40 Seat[34] 41 Seat[47] 42 Seat[49]

43 Seat[51] 44 Seat[53] 45 Seat[55] 46 Seat[36] 47 Seat[57] 48 Seat[38] 49 Seat[59] 50 Seat[61] 51 Seat[40] 52 Seat[63] 53 Seat[42] 54 Seat[44] 55 Seat[46] 56 Seat[48] 57 Seat[50] 58 Seat[52] 59 Seat[54] 60 Seat[56] 61 Seat[58] 62 Seat[60] 63 Seat[62] 64 Seat[64]

Elapsed time 955.49 milliseconds

Party of 128 Guests:

1 Seat[1] 2 Seat[2] 3 Seat[4] 4 Seat[3] 5 Seat[5] 6 Seat[6] 7 Seat[8] 8 Seat[7] 9 Seat[9] 10 Seat[11] 11 Seat[13] 12 Seat[10] 13 Seat[12] 14 Seat[15] 15 Seat[17] 16 Seat[19] 17 Seat[21] 18 Seat[14] 19 Seat[23] 20 Seat[25] 21 Seat[27]

22 Seat[29] 23 Seat[16] 24 Seat[18] 25 Seat[31] 26 Seat[33] 27 Seat[35] 28 Seat[20] 29 Seat[22] 30 Seat[37] 31 Seat[39] 32 Seat[24] 33 Seat[28] 34 Seat[41] 35 Seat[26] 36 Seat[43] 37 Seat[30] 38 Seat[32] 39 Seat[45] 40 Seat[47] 41 Seat[40] 42 Seat[49] 43 Seat[51]

44 Seat[34] 45 Seat[53] 46 Seat[55] 47 Seat[57] 48 Seat[36] 49 Seat[59] 50 Seat[61] 51 Seat[63] 52 Seat[38] 53 Seat[42] 54 Seat[60] 55 Seat[65] 56 Seat[67] 57 Seat[44] 58 Seat[69] 59 Seat[46] 60 Seat[48] 61 Seat[71] 62 Seat[50] 63 Seat[52] 64 Seat[54] 65 Seat[73]

66 Seat[56] 67 Seat[58] 68 Seat[75] 69 Seat[77] 70 Seat[62] 71 Seat[79] 72 Seat[81] 73 Seat[64] 74 Seat[66] 75 Seat[68] 76 Seat[70] 77 Seat[83] 78 Seat[85] 79 Seat[72] 80 Seat[87] 81 Seat[89] 82 Seat[91] 83 Seat[74] 84 Seat[93] 85 Seat[76] 86 Seat[95] 87 Seat[97]

88 Seat[99] 89 Seat[78] 90 Seat[101] 91 Seat[80] 92 Seat[82] 93 Seat[84] 94 Seat[86] 95 Seat[88] 96 Seat[103] 97 Seat[90] 98 Seat[105] 99 Seat[98] 100 Seat[107] 101 Seat[92] 102 Seat[94] 103 Seat[109] 104 Seat[111] 105 Seat[96] 106 Seat[100] 107 Seat[102] 108 Seat[104]

109 Seat[108] 110 Seat[113] 111 Seat[110] 112 Seat[106] 113 Seat[112] 114 Seat[115] 115 Seat[117] 116 Seat[119] 117 Seat[114] 118 Seat[116] 119 Seat[121] 120 Seat[123] 121 Seat[118] 122 Seat[125] 123 Seat[127] 124 Seat[120] 125 Seat[122] 126 Seat[124] 127 Seat[126] 128 Seat[128]

Elapsed time 16,411.42 milliseconds

THE END