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.