All right, so let's get to workshop three. Which, you should be unsurprised, is assignment problem, actually. 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. So, we need to make sure that these decisions are all different. >> Yeah, this is permutation problem. >> Exactly. 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. >> Yep. >> What's next? >> The taste of the last dish, should be sweet. >> Okay. So the taste of the last dish, which is dish[len] should be sweet. Yep. What's next? >> And then we have some complicated constraints restricting the order of the taste of the dish, of the dishes. >> All right, so let's look at the first one. >> No two dishes of the same taste in a row. >> 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. >> All right, so there's that one. What next? And then after a spicy dish, the next dish must be bland or sweet. >> So that means that the taste of dish i, taste of dish i >> Is spicy. >> Is spicy. 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. >> Then the next dish must be either bland or umammi. >> Okay. >> Yeah. >> What's next? >> And then there's no spicy or umami dishes directly after a sweet one. >> Okay, basically means after a sweet dish, we can have bland. We can have spicy. No. >> No spicy. >> Okay. >> Salty. >> We can have salty. >> What else can we have? >> Sour. >> Sour, yeah. All right, all right. Is that it? Well I think that's it for taste. >> Yep, and then we have other constraints on the temperature. >> Okay. >> Okay. >> So temperature constraint says what? 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, If it's hot, then, well and there exist, yeah, j in, so obviously it has got to be from i+1 to len cos we got to the last dish, where the temperature of dish j is cold. >> Yep. >> Yep. Then that altogether implies something. >> Yeah. >> Right so we need some brackets here. So basically we're just taking this complicated sentence and writing it down in logic. So, if we have a hot dish, dish i, and the cold dish, j, which is after dish i, then there has to exist a k in between the two. That is from i+1 to j-1. >> Exactly. >> Where the temperature of dish[k] = warm. Wow! >> We did it. >> Okay, and what's left? >> There's also conditions on the heaviness of a dish as well. >> Okay. >> The banquet cannot have more than two heavy dishes in a row. >> The banquet cannot have more than two heavy dishes in a row. >> Yep. >> Okay, so basically we can't have three heavy dishes in a row, is another way of saying that. >> Yep. >> So if heavy [dish[i]] and heavy[dish[i+1]] implies not >> not heavy[dish[i+2]] 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. >> 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. >> The number of changes in taste. >> Yeah. >> Okay, so then we're going to have to look at each pair. >> Yep. >> And see if there was a change in taste. Hang on, there's always a change in taste. >> That's not true. Is it true? >> 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. >> So- >> And then the changes in temperature. >> Temperature will be that the temperature of dish i is not equal to the temperature of dish i+1. A plus there is better. >> And then one more, the change in the heaviness or the weight of the dishes or the pair of dishes. >> This is heavy dish i = heavy dish. No not equal sorry. The changes we are counting (i+1). All right. And we're trying to maximize. 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. So actually we have to rewrite it. And actually, it's really for every cold dish we need to find another one. >> Aha. >> Right, so basically our logic was wrong. If there is an i dish which is hot, for every dish j which is cold. Right? >> There must exist- >> There must exist, so that's inside this implication, so we've got a bracket somewhere, that goes there. Alright, interestingly that our logic error was shown up by the liveness of the variables. Yep. >> That was useful. All right except now that I've put too many brackets somewhere. So that's that one. One more >> I don't really need that one but, that's simple. All right, now we can set our variable and hope that it all works. 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. All right, so that’s one way of doing the problem. But you should see, we did some complicated things here, look this is a very complicated thing to deal with the heat and we did a lot of things about taste. So, is there a better way of doing this? Yep. >> While these are patterns. >> This is a common pattern which is that we need a sequence of things to satisfy some constraints and we can do that using the regular global constraint. 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 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. So she's going to start in this state. And really if you think about the rules, they're all basically, and we have to remember what the previous dish was. So we can think about basically having six different states, which are basically, the six different kinds of dishes. There's spicy, >> Sour. >> Sour, thank you. >> Salty. >> Salty. >> Sweet. >> Sweet. >> Umami. >> Umami. >> And bland. >> And bland. 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. So it could go anywhere else. And finally, let's use another color. The bland can also go anywhere. 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. 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. 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. I'll start in black color. So basically, we're only going to have to keep track of hot and cold/warm. And this is our start state, because we can do anything originally. Then we can go there, or we can go here and, 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. >> Which has quite a number of arguments. >> It has a lot of arguments, but it's basically going to be able to do all of these things here. Right, we're just going to get rid of all of that, And replace it with one regular. 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. TASTE. And the next thing is the transition array, and then there's the final states. 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. Not how you delete, so basically, we need to build this transition array. So this array is a mapping from 1 to 7, that's the state we're in, and TASTE. Of int from 0 to 7, so this is the key. It's going to either one of the states or 0, representing the error state, right? So it's that. It’s a fixed array. 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. And sour, we can go to bland >> Umami. >> Umami and nothing else, so. 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. 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. 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. 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. >> 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 sequence, so this is why after a bit of this it begins that we might have built these arrays directly. >> Using array comprehension to build another array. >> Exactly. So we've got two states and we're looking at temperatures, there are three different kinds of temperatures. We are going to have the temperature transition array. Now, the start state was one. And the final states were both of them. >> Right. >> Yep, if we remember from our picture here. >> Yeah, all of them. >> Yeah. And then we have to build this array. >> You forgot the semicolon again. [LAUGH] >> My God. Repeated errors. So this is from one to two of >> Temp. >> Temp. Of zero to two. So this is our td array. Okay, this is state one, this is how it started. [LAUGH] So from state one on the cold we go to state one actually, which is which? I think hot is first. Hot, cold, warm. So on a hot we go to state two, on a cold we stay here. And the only thing interesting is in state two, which is hot. On the hot we go here, cold is an error, and warm we go there. Right, now we should be able to run again. >> Still the same. >> Still the same answer. But this is a much more efficient constraint than what we built before, particularly as sizes get bigger. We could think about doing an automata for the heavy but it's such a simple constraint here that I don't think it's going to be worth it. So there we go, we've seen how to solve the feast trap problem. >> Impressive. >> [LAUGH]