Welcome to Workshop 10. This is the second workshop of the solving algorithms course. Jimmy, what's happening? >> Well, in this new workshop here, we are preparing alchemical potions. We saw that Shannon all ready prepared the herbs, and the reason he had to do that was to make alchemical potions to heal the sick children, okay? While there are different potions to make, but the ordering of preparing the potions are important, because some of the potions would be used as ingredient to prepare other potions. >> Yep. >> So we have precedence constraints again. >> Yep, okay. >> And then Shannon could not do all the work by himself, so he has to hire a bunch of alchemists to help him. So every day, Shannon would have to prepare some potions, there is a maximum number of potions that you could do every day, because there's a limit on the equipment that he's got. >> Yep. >> There is also a least number of potions that he would like to make, because he would like to keep the alchemists that he's hiring busy. >> Yep. >> So he's going to hire a bunch of alchemists. Every day he would like to deploy a minimum number of alchemists to keep them busy again. Because he would like to get his money's worth. But then, there's a capacity constraint on the size of the workplace, so he can only put a maximum number of alchemists into the workplace. Okay, now so, of course, Shannon we'll like to save some money, so he would like to minimize on the maximum number of alchemist that he would need on every day across all the data in his preparation process. >> Right, basically because he has to hire the alchemists for the entire period. >> Yes. >> So he's playing for the maximum. >> Yep. >> All right, so let's have a look at the model. So the model here is a bit different from other models we've seen in this course, all right? So here is our reading in of the data. >> Right. >> Right, so we're reading in the number of potions. How many alchemists each of them need? A minimum and a maximum number of potions we have to make on each day. A number of maximum alchemists we have to use in each day, and a prerequisite between the potions, right? Here is a two-dimensional array. Okay, but here we've got three different ways, all right? So we have seen in multiple modelling in previous courses that we can often model things in multiple different ways. So, here we're going to model them in three different ways and every all of the constraints are going to be there in three different ways. >> Okay. >> Okay, so the first way is for every potion, we just decide which day do we do that on. >> Right, that's the basic- >> That's the fairly easy way to think about it. We can also for every potion for every day, we can have a zero one variable, or true false variable, if it's actually saying do we make that potion on that day. >> Yeah. >> Okay, which is often what we do if we're trying to write a MIP model for doing this directly. Then, another way of thinking about it is, on every day what potions do we make, right? >> Right. >> Which is a set of potions. So we decide the set of potions we make on each day. >> So this is a standard technique when we are modeling a rostering problem? >> Yeah, exactly. >> Yeah. >> All right, so we got some auxiliary variables just to count stuff, right? >> Mm-hm. >> So how many potions do we make on each day? That's a number. And how many alchemists are working on each day? >> All right. >> That's another one. And then there's our objective, which we're trying to minimize. Okay, so let's look at some basic constraints. Okay so we need that the number of alchemists working on each day is less then or equal to the objective, because that's just maximizing. Saying the objective is the maximum amount of working things, right? Then we need the potion prerequisites. >> Mm-hm. >> Now that's pretty easy with the day variables, so we just say okay, this is the one that has to be finished first. Then it has to be on a day, that's before the day where we do the second. Okay? We can also map it using these boolean variables, right? So basically this is calculating the day when the first one was done. And this is calculated in the day when the second was done, and making the same constraint, it ends up being a linear constraint. We can also do it with the SET variables, it's a bit trickier, all right. So we're basically saying okay, if we look at all the days and we have that this portion is done on day d1, right. Then if we look at all the days before d1, then we can't have the second portion done on that day. >> Wow, in this way of expressing the constraint, we are using if then. >> Yep. >> And we are also using negation. >> Well yeah, a negation of a boolean isn't too bad. >> Okay. >> Okay. >> Yeah. >> Yeah so it's bad, but it's not too bad. >> So essentially we have three different ways of making use of the three kinds of decision variables to express the constraint. >> Yeah, the is a constraint. >> Right. >> Right, they're all there at the moment. >> Yeah. >> Right and we're going to do that for every one of the constraints for the problem. Okay, so we have to keep track of the number of potions we've made in each day. >> Yeah. >> Right, so we can do this by just summing up for every potion, right, if it's made in that day. Okay, so that's obvious way of doing it. Very similar if I've got the booleans. I'm just summing up the 01s of which potions are on that day. >> Yep. >> But if I have the potions, right, which actually gives me the set. I just need to get the cardinality, right. So it's simpler, this is simple in the SetView. All right, what about the calculation of how many alchemists are working each day, it's very similar as to what we did before. Here we're just saying if we do this potion on this day, then we have to have at least this many alchemists that portion needs. And that gives us the total working on that day. So I'm summing across all potions. Very, very similar in the boolean view, right? >> It's just that this expression here day(p)=d is exactly equivalent to this potion, potion_day[p,d]. And for the SetView, we can actually make use of a global constraint, which is isn't normally visible, but it is available. And this is basically something which given the set, and it says for each of the elements, so the potion is the set of elements and alchemy is the weight of each element, it's going to calculate the weight of elements in that set. >> Wow. >> Okay, so this is exactly what this global constraint does, and we're going to need to have this definition here, just to make sure that it gets through the flat sync. >> It's a predicate. >> Exactly, the solver g-code understands this constraint. >> So in this exercise here, we can really see the power of multiple modeling, right? I mean it allows us to look at the problem from different viewpoints. >> Exactly. >> And we can also see that some of the constraints are easier to express in a particular viewpoint. >> Exactly. >> Right. >> All right, so then we've got some more constraints. So potions are not assigned to two days. Okay, so that's obvious in the day view, right? >> Right. >> Because the day view, I look at the potion, it's given a day. It can't be given two days. >> Exactly. >> So that always happens. Not obvious for the other ones. So for the boolean view, well, I sum across all the days and I say the number of days when I make this potion has to be equal to one, which means only one day can be true. And for the SetView, I basically need that the sets for each day, they all have to be disjoined. So that's the global distraint, all disjoined. >> So a potion cannot appear in more than one set. >> Exactly. >> Yeah. >> Basically two sets have to be disjoined >> All right, now remember we've got multiple viewpoints so we have to make them agree. >> Yeah. >> So if we're going to use two viewpoints we have to make them agree. We can channel between day and potion day. >> Yeah. >> And this is basically exactly the statement we said. Potion day pd is exactly the same statement as saying the day that I made potion p was d. >> Yeah. >> Right, we can channel between potion day and the potion view, which is almost the same, right? If I made potion p on day d, then it was p is in the potions that are made on day d, right? And for this SetView and the assignment view, then we have this int_set_channel, which does exactly that. >> Global constraint. >> Exactly, because this is a common thing that happens in mobile. Right, so we have it. So, just no, nothing wrong with not having global constraint here because in fact, there's not much you can do better than these definitions, right? >> Sure. >> Okay, we're also, in order to make our model strong, we're going to add some redundant constraints. So here it's just making sure that if we add up all the amounts of working on the days, it gets the total alchemy we need to do, which is the sum of an alchemy of all the portions. And basically if we add up all the numbers we have to get to the number of portions, right? So that's basically just redundant constraints. Here's a tricky one and this is looking for everyday, we're sort of looking at the number of portions that are made after this day, right? And we're saying well, that total amount of alchemy that we're going to use after this day has to be greater than or equal to the number of days left times the minimum number of algorithms we can use every day, all right? And it has to be less than or equal to the number of days left times the maximum amount we can use, which is the objective, right? So it's basically your redundant media constraint, but let's just look forward to say, well, if all of these portions are still unassigned, they still have to be done. And if that ends up being too expensive in the future, then I can just stop. >> My understanding is that a constraint is redundant if it's not going to change our solution, right? So essentially, in terms of getting a solution, the redundant constraints are not needed. But we will put them here if they can help us to increase propagation. >> Yes, exactly. >> Right? >> Yeah, so we don't need this constraint. Any of these constraints marked redundant we can remove. >> Right. >> And that's part of this workshop. You'll have to remove all things which are marked redundant. >> All right. >> Okay, we've got this, the day view. Then we can do the same thing with the portion day view and with the portion view. Although notice they're not so clever, here, we're actually making use of the fact that we can write down something directly, right? That the day of this portion is after some day right, and that's just a very single simple boolean. Here I have to calculate an expression, so it's not so direct. Okay, so now we have this complicated task, Jimmy, we have to work out the best model and the best search at the same time. So how on Earth are we going to tackle that? >> Now first of all, this model would work, right, you're combining everything together, it would work, right? >> Let's run the model, that's a good idea, it better run. Otherwise, [LAUGH] >> [LAUGH] I hope so. >> Something's wrong. [LAUGH] I can't spell indomain_min, that's what's wrong with that. So that's okay, line 134. >> Search1, there, yeah, okay. >> Okay, that's not too bad. >> Nope, okay. >> All right, let's try again, live action, okay, yay. It works, and we should probably turn on statistics. And why don't we also put a time limit of 6,000 milliseconds? So that we're not waiting too long. All right, okay, so now, we can actually get some statistics out of this. You can see that we've found, okay, this first solution is fairly straightforward. We can get a solution in 17 failures. All right, so now, our current lead, by the way, our searching we're doing, is we're just using the data variables, we're going in order, and we're saving over the minimum values. Kind of like, very just naive. But the good thing about this search is it doesn't care about the constraints. It can't be changed by the constraints, right? Basically we're always just taking the next variable, saving to its minimum value. So basically we fixed the order of the search, independent of the constraints. >> Okay, let's talk about model again. >> Exactly. >> So, right now, we have a combined model, combining constraints and variables from three different viewpoints. And then they are channeled together. Okay, so they work. >> Yep, result. >> So in essence each of the viewpoints, the variables and the constraints, they are redundant with respect to the other viewpoint, right? So we could actually comment out one of the viewpoints and see how things will be like. >> Yeah, yeah, actually, why don't we just comment out everything except for the day view, right? So that's the primal view, the most obvious way we're writing it. >> So we are only commenting out the constraints, right? We'll leave the viewpoints, the variables there. >> We'll leave the viewpoints. So basically we're keeping everything here, which talks about the day view. >> Yes. >> Doesn't matter, the day view doesn't meet any of these. Okay, we don't need any channeling. >> Why not? >> Well, if we've only got one view left over, there is nothing to channel between them, right? >> Right. >> I mean, we could leave a channeling in just to fix the variables. >> Exactly. >> But and sometimes this is why we just leave the variables free, and we're done. All right, so then they'll just be set to arbitrary values. Really should have thought about the easy ways of commenting this out quicker because I'm going to have to comment back in at some point. All right, so if we had over four with all the constraints, right, the search shouldn't change. So we're hoping to get the same number of failures. But we've changed. We might get more failures now, because we actually have commented out something that might be helping. Okay, for this tiny example, no more failures. If we look, the time went down quite a lot, right? Well, no, not really. >> Mm-hm, because it's a small example. >> Exactly, propagate is 11,000 to propagations 9,000. That's a really tiny example, let's try a bigger example now. Okay, so alchemy one, we're running. >> Okay, timeout. >> We can't actually prove alternality, right, with this example. So, can we do better, right? If we went back to the original problem, I wonder if I can load that in. I might have a copy sitting around, so I don't have to uncomment [LAUGH]. But I need to set up the search to be the same, so and currently, we're doing int_search(day, input_order, indomain_min, and the useless complete. [LAUGH] >> [LAUGH] >> All right, so if we run this one, >> Still times out. >> We only got the same thing. Nodes and phase, it's a bit hard when we time out, it's a bit hard to tell. >> Right. >> Okay, so you can see there phase 300,000 versus 50,000. >> Right. >> Okay, so that might be that we've got a small search base, or it might be because we're actually just doing less nodes per time, right? So in six seconds, we can traverse less nodes because we've got a much bigger model. All right, let's see if we can actually finish one of these off. Okay, that would be better. Right, so alchemy two with this search space, we can actually prove optimality. So there was our basting with all of the constraints in. Let's run it with only the primal model, okay? So now we can compare. So what do we see? I think 0.035 was the time, this was 0.147, so definitely the other one took longer. What about failures? 325 for the primal version. >> Looks like the same. >> 325, so in this case, we're basically driving straight to the same problem, and we're not getting any more solving. If I run this one, I can approve also. Or is that the same one? I think I didn't select it, that's it. Ideally, what I want to do is find one which I can actually prove optimal. I can't prove optimal in 30 seconds using that one, and I probably won't using this one either. But maybe,... >> Nope. >> Not in there. >> But 33, in fact I get a lessor objective right? I got further. >> Yeah. >> So obviously, the primal only is better than our base in this example. But why don't we look through the base. In fact, this time why don't we save it as a new one. So we can look through and remove bits that we don't need. All right, so what we want to do is look at every constraint and think about which is the right way to specify it. >> Right. >> Okay, so what about the potion prerequisites, which do you think is the best way of specifying this constraint? >> Wow, from my gut feeling, I would select the one that is the simplest. >> Exactly, okay, and that's very clearly the first one, here. So let's comment out those ones. You could just highlight all the lines that you want to comment out, and then- >> I would just more mistakes- >> [LAUGH] >> If I tried to be a power user. Jimmy's a power user. >> All right, number of potions made on each day, which do we think is the most simple? >> Mm-hm. >> Well I think the last one, right? Is just a single, just looking up the cardinality, right? So that looks to be the most simple, so let's keep that one. Yeah? >> Okay. >> All right, the calculation that the alchemist is working on one day, we can see these two look almost the same, but this one we've been able to use a global. So hopefully, the global is going to help us, right? So let's get that. Okay. So these are redundant. No. These we don't need, right, because we're keeping the day view. Although we might want to keep that as a global as well. It might be helping us. We don't know. And now, we're only in the end if you think about it. We only ever used the day and the potion's views. And we've never used the potion day viewc. So we don't need that channeling. >> Mm-hm. >> And we don't need this channeling. Yeah, we just need this channeling. >> Yeah. >> Okay, we'll keep all the redundant constraints. Now for the redundant linear constraints as we were talking about earlier. Since this actually makes use of the day variables cleverly, it's likely to be better. It's simpler than these other versions. Now we hope that we've improved our model. Okay, now again, it's hard to tell with this search strategy. This is the problem that we're stuck with a fix search strategy, which isn't very good, right? >> Right. >> And that's the only thing we can really compare. So what about we try a different search strategy. You have prepared five. >> I have prepared a number. So let's try search two, so here we're just doing the day in order, and now let's take day with the first fail. So we'll take the one with the least possibilities and set that up. So that's generally a good idea right? >> Yeah. >> So if we run alchemy 3 well. >> Wow. >> Remember we didn't in 6 seconds, we got to an answer of 32. Now in 0.025 we come to an answer of 30. >> That makes a big difference. >> This seems a lot better, okay? So that currently alchemy is our primal only. Let's add in our base as well, which was everything. That was the original model with everything in it. And change its search strategy to be the same, so I can see, this is use first fail, all right, so if you run our original model, we can solve it, 104, failures is 87, let's see how that compares with back here. With the primal only, okay? >> Same thing. >> So, same thing. So, in fact, by removing all those constraints, we didn't change the search base. What about our new one, which is, we hope, is the best one. I'm going to find the search strategy, change that to first fail. Run that okay 87. >> Seems to have space. >> So now we just gotta look at, let's say propagations 22,000. But this one 0.019. So the big model which is this one had stacks of propagations 115,000 all right with 0.104. >> So it's faster. >> Yeah, so our new model is faster so less propogations even than this one and it's slightly faster I think. >> Yeah I think so. >> Yes it is slightly faster okay. So that seems like once we've got a good search strategy, now we can sort of compare these things better, because we know that they're finishing off right? >> Right. >> And what other searches can we try? Well, all right so we haven't tried searching on the potions view. >> Right. >> All right of course if we can't, because we've change this let's copy this because the diver was less it's no point. Comparing in it what we need to do is put it here right? So remember this has got the potion views left, this is our optimal model or our best possible model where we've kept the best version with the constraint. And we'll compare that with the base model where we kept all of the constraints, every version of every constraint. And we'll see how it goes. If we try the base first, okay? So the set search isn't doing so well on this version. Right? It ran out of time. I think it got the optimal. 30 was the optimal as I recall. Yeah, but it could improve optimality. Let's go to our optimize version. Okay, so it's going to have basically the same behavior. >> Yeah. >> So for this example, definitely the database search was better. All right. We can come back and look at some different things. So what about doing a search on the portion days? >> Mm-hm. >> Right? How does that compare? And of course to do this properly, we should actually We should actually try everything instead of big scripts etc., etc. [LAUGH]. Will leave you to do that. >> Too many possibilities >> Yes exactly. Okay, right so we can't really compare our optimized model, remember we've got read of the portion earlier. So we can always try the base with this version >> Mm-hm >> Right? Or we can get same point, not really helping us. Okay, yeah, so no different. Right, if we can't prove optimality let's go back to two which was maybe easier. Maybe we can prove optimality, no not with this search. Right. The problem is now the Booleans, we've got nothing. At least with the first fire we're actually taking advantage of something. All right. But let's look at this one, which is I searched a bit around and this was the best one I could find. That's sequential search. >> Okay, so think about this. We can use sequential search, and also we can use dom_w_deg which remember is our failure based search. >> Okay. >> So here our search says we're going to first search on the objectives. So we're going to assume that we can get a minimum value. And that really means that this is just trying to find a solution which actually fits the objective. We're using dom_w_deg so we're going to concentrate on variables which cause failure. And here we're just using random values. All right, just putting in random things because in some sense, once we fix the objective it's like packing potions into boxes to make them fit. All right, if we try that, this is our base version, okay? >> Wow. >> Okay, we can quickly find the optimal solution there. What if we do the same thing on our new search version? And hopefully now we can compare these two. So that one was 117 failures. >> Wow. >> Okay 26 failures, okay? >> No, 7. >> 7 failures, okay. >> [LAUGH] >> So it turns out if we try, We should be able to try most of these things. That we'll get very, very quick answers out of our optimal model. Well that one took a while. It still was able prove optimality. If we go back, try the same search on our nonoptimized model. So remember it's the same search. Might have been, it's faster. Okay, in this case you can win and loose, because they're dynamic searches, right? >> Right. >> So, but I've done a bit of looking around the benchmarks, and remember there's a whole hundred other benchmarks which are bigger. And at least this was the best search that I could find. >> I have a feeling that our base model involving all three viewpoints in there, it might not be the most efficient model, but it could be the most robust. >> Yes, exactly, because we're going to get the most amount propagation out of it. >> Exactly. >> Right, because it has the most constraints in it. The question is do we ever lose some propagation? And it is the case, I've checked on a tiny example, that our slimmed down version, where we just kept the potion, and the potion day variables actually can lose some propagation. But the pay off is that it wins. >> Yeah. >> Unless of course, and this is the problem about comparing dynamic searches, right? >> Yeah. >> So sometimes the dynamic search can just win big. >> Yeah. >> But if you look across the average results, then this was the best search- >> Mm-hm. >> We could find. And if you take that, and run it on the bigger examples, and you'll need a good search to run on the bigger examples, to get any answers, then this also turns out to be the best search, that I could find, at least. >> Which is interesting, that you use this input order. But surprisingly enough, this other search that we saw, this search on potions was not nearly as bad as you think. It's actually one of the most robust searches there are. >> Yep. >> Okay >> Do we have any data file that is difficult enough so that we will have to try restart as well? Well, yes so, [LAUGH] that's a good point. We can try restart by going into here, and adding, let's choose the simplest kind of restart. So, we won't change any of the default things, and we use luby, right. So luby is a very robust kind of restart, because it just tries lots of small restarts and a few big restarts. because if we take our optimal model and we run it now with luby. Now I just see what we ran. Okay and there's base, there's new with alchemy-5. It took, so we were unlucky, right, for alchemy-5, remember. >> Yeah. >> And now we're running alchemy-4, so what happened? Yes, okay, let me run alchemy. >> Why don't we start all over again? >> Yeah, exactly. So alchemy new. I want to do- >> This is 4. >> Yep, I want to run 5 don't I? >> Yeah. [LAUGH] >> Okay, that's what I ought to do. Okay, all right [LAUGH]. >> Okay. >> Okay, alchemy-5 with restarts, 0.013 seconds, 20 failures, 3 restarts, and we got the optimal. If we compare that, if I go and- >> Without restart? >> Without restart Go back and run it again, right? Remember, this was our bad case. >> Right. >> Right? >> Okay. >> So this is the thing that restarts give you, right? >> Yeah. >> Here we were just unlucky, it's a good search regime, but we just got stuck, we found some bad decisions at the top and we couldn't undo them. Right by turning on restart suddenly it's almost instant. >> And only in three restarts. >> Yes exactly, we don't need that many. We were just unlucky right at the top of the search tree here making a decision that we couldn't get out of. Whereas here we've restarted, undid that decision, and found a better solution. And indeed if you take this combination, it's the combination with restart which really makes this robust. >> Mm-hm. >> Right? But actually restart improves almost all of the search strategies that I played around with for this example. Just because it's very easy to get stuck in the wrong place and then you can take a long time to get out of it. And restart will stop that. So restart in general was, it may slow you down slightly. But it just makes search much, much more robust. >> So we have just demonstrated how we can combine all these advanced search strategies, including sequential search, restart, as well as failure based search. >> Exactly. >> How they can do on the- >> Exactly. So here, we're using kind of our most powerful variable selection heuristic. We're actually not, we're doing the search in a different direction than normal. We're actually fixing the objective. So we're trying to get the smallest possible value. It means then actually you'll only ever get one solution, right? because the first solution you find, will actually be the minimum. Because once you find a solution with objective 26 you're not going to try one with objective 27. >> Right. >> But in this case for these examples we can do it very well. Right, so not a good, if you get really, really big hard examples that we can't solve in time, this is a terrible search. >> Right. >> Right, because it only either finds the optimal solution, or finds nothing. >> Right. >> But it turns out for these problems, even the bigger ones >> We can easily solve them.