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.

Â 25:43

>> That's right.

Â >> Thatâ€™s what we should be doing.

Â Okay, so it shows you that maybe, it's interesting that we got exactly

Â the same objective at least, maybe it's a different solution, I can't remember.

Â Now since it's the temperature

Â