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 define all unknown variables in the array “SeatVariables,” each element of which is defined from 1 to the number of guests.
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 the number of elements in the array of Guests.
We will use the following top-level decision “Define” for the problem definition:
We will use the table “SolverPreProcessor,” which will specify the names of SeatVariables before even creating the proper decision variables with the name “Seat{{Name of Guest}}” and the domain VarDomain (see the glossary):
Then we should post seat constraints:
The first one states that all Seat Variables should take different values. The second constraint assumes that the first guest is always sitting at the first seat (as all other decisions will be simply symmetrical).
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 “IncompatibilityRules” 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 rules “PostIncompatibilityConstraints”:
This decision imposes constraints that hopefully are intuitive. Note that “constraint1 -> constraint2” means that if constraint 1 is satisfied, then constraint 2 should also be satisfied.
Problem Resolution. We may rely on the predefined search strategy “SolverFindSolution” supported by Rule Solver. We also may print all found values for SeatVariables using the action “SolveLogVariables”:
Main Decision. It relies 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
openrulesdecisionmanager.com 