0:22

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.

Â 0:49

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.

Â 1:52

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.

Â 2:23

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.

Â 4:46

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.

Â 6:48

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.

Â 7:16

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.

Â 8:23

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.

Â 9:45

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.

Â 10:47

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.

Â 12:07

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?

Â 12:56

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.

Â 14:18

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.

Â 15:07

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.

Â