0:11

All right, so basically,

Dao Chan has to decide which dishes to put in which position.

So it's basically assignment of positions to dish, all right.

>> Yep.

>> So let's open up the starting model which has the data in it so

we're going to have some dishes, each have a taste and a temperature, and

some of them are going to be heavy and we're going to have restrictions on them.

Basically here's our decisions, right?

For each course, what dish do we do then?

>> All right.

>> So, it's an assignment sub problem.

So, the first thing we should remember is, we can't use any dish all at once.

1:05

Now, we've got these, lots and lots of decisions about what's going on, right?

>> Yeah. >> So, it's probably going to be worth our

while keeping track of, Well we don't have to do this.

Let's do it without this.

Might be worth introducing as a variable just keep track of the taste of each dish

at each time the heat and the heaviness but we can do it without it.

So the first thing, right, is to think about the taste constraints is

The first dish should be.

>> Salty.

>> Salty.

So, right?

We know that that's the first dish.

That the taste of the first dish, should be salty.

Yep.

2:20

>> Okay, yes, that's a good point.

So we're going to basically have to look over all pairs of adjacent dishes.

>> Yes. >> So this is 1..len-1, and

say the taste of dish in position i is not equal to the taste

of the dish in position i+1.

>> Small cap.

Yeah.

3:09

That implies something about?

>> The dish after it must be bland or sweet.

>> Right, let's just put it in brackets to make sure taste [dish, or

actually we can do it without a disjunction, let's do it this way.

Taste of [dish[i + 1]] is in the set.

>> Yep. >> Bland, sweet.

>> Yeah.

>> All right.

>> Okay.

>> We're probably going to get something very similar to that next, I think.

>> Yep.

[LAUGH] >> What's the next one?

>> After sour dish.

>> Yep.

4:44

Between a hot dish, and later, a cold dish, there must be a warm dish.

>> Okay, so this is going to be a bit more complicated.

>> You think so?

>> Right. So, if we think about for

all dishes, well, obviously, I mean the first.

Mainly this one, because if you have a dish after it, and,

it can't be the last dish.

Well this would be len- 2.

>> No because imagine that we had a hot dish second last and

then a cold dish last, we have to have a constraint to disallow that.

>> Right, okay.

>> Okay, so if this dish is hot, so

this is the temperature of dish i,

7:30

careful about the precedence here.

But I think that's right.

The conjunction binds tighter than the application.

>> Okay. >> So, that should be great.

>> It should be i+2 there.

>> It should be i+2, thank you Jimmy.

7:45

>> The power of pair programming.

>> Exactly.

So what else do we have to do?

Now we have the objective, I think.

>> Yeah, exactly.

>> So what are we trying to optimize?

>> The sum of the value of the dishes.

So basically that's- >> There are few components.

The sum of the values of the dishes.

>> So this is the sum(I in 1 .. len) (value[dish[i]]).

>> Yeah.

>> Yeah.

>> No not yet.

>> Okay. >> And then plus.

>> Plus.

>> The number of changes in taste.

8:40

>> Well, there's always a change in taste, because you can't,

no that's a change in taste.

Is there always a change in taste?

Yes because you can't have two dishes at the same taste.

Mm-hm.

>> Okay, so that will always be len-1

for the changes in taste.

>> Yep.

10:03

All right, let's see if it works, hey.

Let's load in our data file.

All right,

there's our data

file and >> unidentified identifier,

j 33, exists j in (mumble jumble).

Undefined identify >> at 33.

>> 33.

>> Aha.

>> It's because this brackets.

All right so, this has to be within sides it exists.

11:47

Okay, so we've got there.

Now we haven't made it output everything possibly that we need.

But it seems to have worked.

Well, it hasn't, it's not telling us the objective.

We can find the objective value- >> Yep.

>> By turning this into a constraint just so

the default output will give us what we want.

All right, optimal value of 46 which is

better than the one shown in the handout.

>> [LAUGH] >> So

the ones in the handout are not always the optimal ones.

Be aware of that.

12:52

But we have to understand that we can turn this into a finite automata.

All right, Dao Chan has to decide the order of the dishes, and

there's some complicated sequencing constraints here.

>> Yes.

>> And so, here we can make use of another combinatorial substructure,

which is common in lots of discrete optimization problems.

And that is, basically where we're going to

13:17

define the possible sequences using a finite automata.

And then we're going to use the regular constraint

to enforce the constraint that the sequence matches that automata.

So let's think about the automata that Dao Chan has to make for

the tastes of the dishes.

So we have some start state.

14:10

All right.

So, in a start state, what can she do?

>> Well, the first dish should be salty.

>> Right, so the only place we can go to from the start state, is salty, right?

And then there's other restrictions.

So, the final dish has to be- >> Sweet.

>> Sweet.

So really, the only way we can end this automata,

that's the only final state is in the sweet state.

>> And then there is another constraint.

>> Okay. >> Saying that after spicy dish,

the next dish must be bland or sweet.

>> All right, so, the only way we can leave the spicy state,

is we can leave to bland.

>> And sweet.

>> Or sweet.

>> Yeah. >> Yeah.

And then there's another one.

After a sour dish, the next dish must be bland or umami.

>> Okay. After sour, we can go to bland.

>> And.

>> Or umami. >> Umami.

Yeah.

And no spicy or umami dishes directly after a sweet dish.

>> Okay, so that means from sweet, we can't go to spicy.

And we can't go to umami.

>> Right.

>> We can go everywhere else.

Right?

You should remember that we can't go from spicy to spicy either.

>> True.

>> Because you can't do two of the same taste in a row.

>> That's right. >> So sweet goes to everywhere except,

which was it?

>> Except spicy or umami.

>> Okay, so it goes to sour, it goes to salty, and it goes to bland.

>> Right.

>> All right.

So we've actually seen what happens in the spicy, the sour, and the sweet dishes.

We've got to also think about what happens when we leave salty,

if we're in this state, where can we get to, umami and bland, and

I think Since we don't have any constraints there.

So that means after salty, we can go almost anywhere except itself.

>> Right, anywhere except yourself.

So salty.

Let's use a different color, just to make it a bit clearer.

Can go anywhere and umami is the same, can go anywhere.

16:29

So we're getting quite a few arcs.

>> Yeah.

>> Which is sort of the nature of finite automata, but basically,

that's encoded the whole thing, and we can number these tastes.

Let's number that 1, 2, 3, 4, 5, 6, 7.

>> Yep.

>> Okay, so that's the entire finite automata,

that expresses where you can go,

what sequence of tastes you can have.

So we can also do an automata for the heat of the dishes.

It's a bit simpler, so we're in some start state here.

And basically we can do- >> Hot.

>> Hot >> Cold.

>> Cold >> And warm.

>> And warm.

17:23

And obviously, we can do any dish first, all right?

>> Yeah.

>> And the only real restriction is from hot, we can't go directly to cold.

So for hot, we have to go to warm or itself,

so here we can't have two hot dishes in a row.

>> Yeah.

>> From cold, we can go anywhere.

And from warm, we can go anywhere.

17:49

So there's our automata.

>> Right. >> But

here it might make a bit more sense.

Let's label the edges with what was going on because this is what's really going on,

right?

>> Yeah. >> We're just remembering which was

the previous thing, so this is hot coming in, hot coming in,

it's warm, cold, and that's cold, that's warm, and that's warm.

And if we look at this automata, and what's the final state's obviously,

any state is the final state, right?

>> Yeah.

>> Even this one.

And we can actually minimize this automata because really,

there's no difference between cold and warm.

They can go. Basically they can take anything.

The only difference there is hot.

>> Right.

>> Right, so we can actually minimize this automata to this.

19:02

That's the thing, but now we all want to keep track of what happens.

So hot we go here, hot we go here, warm we go down, but cold we don't.

>> Right.

>> Right that's what's different.

And here cold and warm, we stay in the same place.

And this is a minimal automata doing the same thing.

>> It's so much simpler than the other one.

>> Exactly, now we should be used to, from automata theory,

that we always want to have a minimal automata to do what we're doing.

>> Yeah.

>> All right, so here's the automata we built for the taste.

So how are we going to represent that in our model?

So we're going to include the regular constraint.

19:54

Now I've got to remember what the regular arguments are.

>> The first one, I think is the list of variables?

>> So this is the list that we're constraining, so

this is our dish variable.

>> Exactly.

>> Okay, now do you remember the next?

>> [LAUGH] >> I think it's the number of states.

So the number of states is seven.

Yeah, right.

We've got to have a picture of our states in here.

The next thing is, I believe, the start state.

Yep.

>> Not the number of- >> Maybe it's the-

>> The number of transitions.

[CROSSTALK] >> The set>>The alphabet>>Yep, so. What we are,
the alphabet is dishes.

>> Yeah. >> No, it's tastes.

>> Tastes.

>> What is it called?

TASTE.

20:49

Is that it?

>> The start state, before the start state.

>> And the start state.

>> Yeah. >> So the start state is one.

>> Yeah.

>> Right here.

All right, so we're going to have to build this transition array.

The final states we know, the final state is only state five.

>> Five, yep.

>> So we can just put that in.

21:38

Now let's set it up.

And what we're going to do is use our picture here.

So in state 1, right, it's only on salty that we go anywhere.

So everywhere else is an error.

So 0, 0, salty is third.

So that's state 4.

>> 4.

>> Then 0,0,0 so that's what we do for the six possible tastes.

All right, state 2.

We're in spicy, so we can only really go to two places.

We can go to bland, and gee,

it's hard to read this, isn't it, and sweet.

So sweet is the fourth entry, so

we go to state 5 on a sweet and state 7 on a bland.

>> Yep.

>> Yep.

22:41

Right now salty, basically we can go everywhere but salty.

>> Except itself, yes.

>> Right, so basically we're going to, so 2, 3, salty is 0.

>> 0, yeah.

>> 5, 6, 7 so this particular automata has very simple shape, basically.

Sweet again is the same, right.

No, it's not directly up to sweet, we can only go some places.

Salty, sour, and bland.

So 0,3,4,0,0,7.

23:15

Yep, umami can go everywhere but umami,

which is itself, so that's 2,3,4,5,0,7.

And bland can go everywhere but itself, 2,3,4,5,6,0.

>> 2, 3.

>> 2,3 thank you.

These are not easy errors to find once you've built your model.

Now hopefully, that should do everything and run the same way.

Oops, except that I've failed to put a semicolon.

23:53

Yep, and we've forgotten the type of regular.

All right, so let's look up the type of regular.

I won't need a finder, I need a browser Where's the browser?

>> This one.

>> Okay.

[SOUND] Okay, let's just go to minizinc.org.

We go to the resources and we go to the global constraints.

24:16

And let's look up, I think it's extensional constraints, there we go.

Okay here's regular.

So there's our array of variables, Q is the number of states.

>> The number of states.

>> S is the number of the values.

There's the transition array, okay so the only thing we got wrong was that

this is not taste but in fact the number of tastes, which is 6.

All right, And off we go, we found the same optimal solution.

>> Yep.

>> Now we can do the same thing for our?

>> Temperature.

>> Temperature, >> Which has a much simpler automata,

actually it will give us a much better result than this.

So let's get rid of that and replace with one regular, so

now it's the temperature [CROSSTALK] >> Of dish again.

>> Dish.

No, it's not dish.

(Mumble jumble)

(Mumble jumble)

This should be taste, it's the array of tastes.