Liu Bei decided to recruit some scholars to assist him with administration and warfare issues. He invited 20 famous scholars to visit his house. He prepared five tables, each of which would accommodate at most five scholars. He needed to arrange the scholars seating according to several conditions. Firstly, no scholars could sit alone. Secondly, some scholars were enemies, and thus couldn't be seated at the same table. While those that were friends needed to sit together. Thirdly, some scholars with the highest reputation rating, who were considered keys figures, needed to be separated to different tables in order to liven their discussion. >> [APPLAUSE] >> Besides satisfying these conditions, the main goal of their seating arrangement was to use as few tables as possible. An additional goal was to reduce the gap amongst reputation ratings so as to avoid embarrassment. Liu Bei pulled out the tablet to figure out the best seating plan. [SOUND] >> So Liu Bei is trying to recruit talented people to help him in the fight against Cao Cao. So what he's going to do is invite all the scholars available to a big feast, and they can talk to each other, he can meet them all, and he can try to recruit them in to help his army against Cao Cao. So, it's basically a seating problem. He needs to place all these scholars down in a seat for the banquet. So we've got this whole list of scholars down here, and each of them has to be given an individual seat, obviously. Now, obviously there are some rules about banquets. We don't want to have just a single person sitting on the table, that's no good. They're not going to enjoy it. They're not going to be interested in joining Liu Bei and his fight against Cao Cao. So we have to have at least two people on the table, or a table can be empty. We also don't want to put two enemies on the same table. So these scholars are vibrant personalities, and some of them don't like each other. So that would be a bad idea. They wouldn't enjoy and they wouldn't be interested in joining with Liu Bei. Now each of the scholars has a reputation. So this reputation rating for every scholars, and indeed the key guests are those with reputation 10. So these are basically the most important scholars that Liu Bei is trying to attract. So he wants to treat them separately. So the key guests will be kept on separate tables. So not only will this lift the level of conversation at each table. Where we have the brightest scholars separated, but also it makes them understand that they're special. And it means that if we had two key guests together, they would probably spend most of the time talking to each other, and the other people would be not so impressed with the banquet because they wouldn't get to interact. So we're going to make sure that key guests are on separate tables. And then we have a lot of friendships amongst the scholars, and of course if we put friends on the same table, then that's going to make them enjoy the banquet more, so we're going to make sure that the friends are placed on the same tables. And our primary objective is basically to use the least number of tables, that's going to give the most number of people on each table, on average, and make the conversations more interesting. Make it a vibrant feast, and attract people to join forces with Liu Bei. Well we're going to have a secondary objective as well, which is also about keeping the discussion interesting, and that is to try and minimize the difference between the reputations on the table. So here we have a table with someone of reputation 10, a key guest, and someone of reputation 1, and that's a difference of 9. And here we have a reputation 10, all the other ones have reputations of 7 or greater than, and so the difference in reputation here is 3. And we think that the conversation on this table with people of sort of equal reputation is going to be more fascinating, more interesting than this where we've got a great degree of difference in reputation. So this is our secondary objective. So that's what we're aiming for. [COUGH] So let's look at the data we need for this. So obviously we have an enumerative type of all the scholars, and for each of them we have their reputation. And where we just keep track of the maximum reputation amongst them because that's going to tell us who the key guests are amongst other things. We also have a maximum number of tables that we can use, T. And so our table is set is just from 1 to T. And then the table size or how many seats are on each table. And then we're given two arrays. So these arrays of pairs basically, each row has two scholars in it. So, pairs of enemies, and pairs of friends. So that's the data that we're going to use. The obvious decision we're going to make is for every table, we choose a set of scholars that sit on that table. Right, so let's go through the model. So obviously we need that the number of people who sit on the table is less than the capacity of the size of the table. So that's straightforward enough. We want to make sure there's no lonely table so we kind of have the cardinality of a table as 1 because that would be one person sitting them by themselves. We need to make sure that every scholar gets exactly one seat. So we split that into two parts. Everyone gets a seat. So we can say for every scholar, there exists a table where that scholar is in the people sitting that on table. And we want to make sure that no one gets more than one seat, we want to give a scholar two possible places to sit. So we're looking at every pair of tables, and we're making sure that the people on one table, t1, don't intersect the people on table t2. So that's going to make sure that the same scholar isn't assigned to two tables at once. So now let's look at the remaining constraints, and we're going to use this not at the same table many times. So it's worth doing a predicate to do that. So we have two scholars, p1, p2, are not at the same table. If we look at every table, and they aren't a subset of the people on that table. So there's a definition of not at the same table. And then we can use that to express some of our constraints. So we know that enemies are not at the same table. So here's a use of a new thing we haven't seen before. Index_set_1of2. Enemies is a two dimensional array, so we're looking at the first index set of enemies which is the set of rows. So basically we're going through every row in this enemies which is a set of rows, each of which is a pair, and we're saying not at the same table enemies [c,1] and enemies [c,2]. So these are the pair of enemies, and we're making sure they're not at the same table. We also need that the key guests are not at the same table. So we're looking through all pairs of scholars where p1 is less than p2, and if the reputation of p1 is 10, which is the maximum possible reputation and the reputation of p2 is 10, then those are also not at the same table. So we're using this not at the same table predicate multiple times. And in fact, we can even use it again here. So we can look through the friends array, just like we looked through the enemies array, and say that since friends are at the same table, they're not, not at the same table. Although if we think back to the use of various constructs we know that using negation is not a wise idea, and possibly we should model this in a different way. So here we've seen the introduction of the index_set function, and what that does is returns the range of an array. So it's very useful inside predicates to be given an array, which we don't know the size of, and be able to use this to find out the size, and do something appropriately. So for one dimension array, index_set returns that one dimensional thing as a set, right? So the index_set of this x is 5 to 9, the set of values that the index ranges over. And we have versions for 2d, 3d up to 6d arrays, and mainly we have to use it up to 2d arrays. So we have this 2d array, which has 3 to 7 as its first index_set, and 2 to 8 as its second index_set. And we can return index_set of the first of, so this is the first index_set of a two dimensional array. The second index_set of a two dimensional array, these are the two values that the index_set will return. And here's a three-dimensional array for example, and we can return the second index_set of a three-dimensional array, here is from 2 to 3. So there it is, the second index_set. So index_set is very useful inside predicates when we are passed an array we don't know the size of to be able to do something with it. So our primary objective, remember, was to use as few tables as possible. So that's just looking at the tables and counting the number where the cardinality was greater than 0. That's objective 1, the number of tables that we're actually using that are empty. And our second objective set is a bit harder. So, we now have to work out the difference between the largest reputation on the table, and the smallest reputation on the table. And so, this is a complex sort of calculation. It's probably worthwhile [COUGH] introducing local variables to do some of these calculations for us. Because it's a little subtle. So this is min reputation's going to work out. So we're going to iterate over all tables, min reputation's going to work out the minimum reputation of a scholar on that table. So what are we doing here? We're putting up the minimum of this set of values. We're looking over all possible scholars. Now what does this expression do? If the scholar is on the table, then it just returns the reputation of that scholar. If the scholar is not on the table, so this is what this is, right? 1- p on the table. It returns the maximum reputation. And since we're taking the minimum, what this is going to do is return the minimum possible reputation of anyone who's actually on the table. Because as long as there's someone on the table, then they will be smaller than this max reputation. So for max reputation, so this local variable is working out the maximum reputation on one of the tables. We can do the same thing, but it's a bit simpler. So here we're taking the max over all scholars of this expression. Now what does this expression do? If the scholar is on the table, then it returns their reputation. If the scholar is not on the table, so this evaluates to 0, it returns 0. And so the maximum of these values, will be a reputation of a scholar who's on the table, or if this table is empty it'll just be 0. Now we can check here. We check if the min reputation is equal to this maxreputation value then we know that the table is empty. And so our objective remember was the difference of the scholar's reputation on the table, and that should be 0. If we used this maxRep- minRep, we'd get a different number. We'd get basically maxreputation as the difference. Otherwise, the table's nonempty. So this is the normal case, and we just take the maxreputation minus the minreputation, and that's obviously the difference. And we're summing those up over all tables. So there's our second objective function. Now, here we've got a multi-objective function where first one to minimize a number of tables, and then we want to minimize the difference in reputations on the table. So obj1 is the important one. That's the most important thing to do first. So what we need to do to make this into a single objective, which is what handles, is we'll estimate the possible values of particularly obj2. And if we multiply the value of obj1 by a big enough value so that it dominates obj2, then this will be correct. So this objective will be correct because if you think about obj2, we've got let's say up to six tables, the maximum reputation difference could be ten, right? That's a ten and a zero actually, it could only be nine. So that could only be something up to about 60. So the number of tables times 100 will always be more important. So this basically will make a single objective out of a multiple objective which forces that the dominant one, obj1, is more important than its minimized first. So let's solve the model. All right, so this looks like a small enough problem. And if we run it, what happens is after ten minutes, still no answer. So, we've gotta think to ourselves. Is there a better model? Can we use some techniques we've looked at before in this course to make it faster? So what's going on here? And the key thing that's going on here is the decisions are really wrong. We're actually making our life very difficult by representing the decisions the way we did. That representation of decisions is useful for some things, but not for most of the problem. So what we should really be doing is decide for every person which table are they on, right? We know that every scholar has to sit somewhere. So that's a much easier decision than each table. What's the set of people that sit on them? We can channel these decisions back to the original decisions. So the original decisions are worthwhile for some kinds of constraints. And we can also use global_cardinality for counting. So that's one of the reasons that global_cardinality was introduced, is if we need to do some counting constraints, then it can do that very efficiently without having to have the set view, is another way of doing the counting. Another thing, very important thing is we can remove a value symmetry. All of our tables are interchangeable. If we took one solution to the problem and swapped all the people on one table with all the people on another table, that would also be a solution. So the table numbers don't really mean anything, that's a value symmetry we should remove that. All right, so let's go through our model and improve it. So here's a different set of decisions that we can use, and we can channel them with the other set of decisions. So every person, so for every person, which table do they sit at, right? So this is nice because every person will only get one seat on the table. That's inferred because there's only value for seat, and that'll get rid of the need to make sure that every person gets only one seat, although the channeling will do the rest. So we can remove this existence and set intersection constraints that we did before. We can make the predicate not_same_table much simpler now because what does it mean to say that two scholars are not at the same table, just means the table where we seated scholar 1, and the table where we seated scholar 2 aren't the same. So that's a much, much simpler constraint, and that was a lot of our model. That means all of these constraints are unchanged, but they still work the same. So enemies not at the same table. Key guests not at the same table. And friends at the same table have all been changed under the hood by changing the definition of the predicate. So predicates here have given us an advantage, they provided a layer of abstraction in our model. And if we change the way the model worked, we only have to change that layer of abstraction. And we didn't have to change the rest of the model. So finally, we can use global_cardinality for counting, and here we can look through the seats, all right? And count how many people occur on each table, and we want that to be between 0 and S, which is the size of the table. And that removes the need for the cardinality constraint. And finally, we can add this value symmetry on the seat variables very simply. Basically the value symmetry says that we're going to use lower table numbers before we use higher table numbers, and so that'll get rid of symmetric solutions where we could swap two tables. Now we run the improved model and solved in less than one second. And you can see that we end up using four tables, and the total difference in the reputation values at the tables is 23. So, what have we seen in this example? We've seen the use of predicates to provide macros for constraints. Predicates allow us to write down a constraint, which we're going to reuse in multiple places. We use local variables to provide the names of expressions, and often it's worthwhile breaking down a complicated constraint or a complicated calculation of some value into little bits and giving them names. So it's easy to understand, and easy to fix if goes wrong. So both predicates and local variables can be useful even if we only use this macro or name once, just for model understanding. But of course once we're using it multiple times as we did for example with the not same table predicate, then it's definitely beneficial. And once we use predicates, then we need to have reflection abilities. We need to be able to look up the index_set of functions, and we often also need to use these variable bounds lookup that we've seen before like lower bound of x, to find the size of something that's being passed into that predicate in order to build the constraint that we want.