Besides the herbs needed to compose the medicine, Shennong Shi also wish to collect the precious herb called Yaocao, that could only be grown on JianMu, a tree that only existed in the heavenly garden. Nuwa led Shennong Shi to JianMu's trunk, and showed him the potions needed for growing YaoCao. When potions are poured on the trunk, tree segments grow, and eventually yield YaoCao. They were 100 potions, each of which were used to nurture one tree segment. and YaoCao appeared at the end of a full branch with 100 tree segments. Each potion was used to nurture different branches, where each branch contained different numbers of leaves with requirements for different amounts of nutrients. To grow a good YaoCao, there were two criteria. Firstly, the total amount of nutrient needed could not exceed the existing capacity. Secondly, for every sequence of consecutive tree segments of a certain length, the leaves contained had to be larger than a threshold to maintain healthy growth. The more leaves, the full branch had, the better YaoCao it finally yielded. Knowing the large number of possible growing schemes, Shennong Shi hoped to find out the method to grow the best Yaocao as soon as possible. Zhuge Liang summoned the dragon of dimensions for assistance from the professors. So, Shennong wants to grow from Yaocao which is a magical herb, which is very valuable. And the way he's going to do this is grow a JianMus, a large plant and the YaoCao will end up growing at the end the tips of particular branches of the JianMu. So, Nuwa has given him potions in order to grow the JianMu. Now, each of these potions will grow some number of segments from JianMus. So, if he uses this kind of potion, three segments will grow out of the current position where he applied the potion, and those segments will have a number of leaves on them. So, the first segment will have eight leaves, second nine, the third four. And they'll require a certain amount of nutrients. So this first segment requires 10 nutrients, a second segment 17, and the third 5. And there's multiple choices for these potions or basically is going to apply the poison's order first-to-first potion, and in the second, and third, et cetera. But the potions are different so, this potion here, this grows four different segments which have different number of leaves and different nutrient requirements. And so he's going to grow segment by segment, first he's going to use the potion A grow the first segment and he's going to apply the potion B after that, et cetera. Now, there's some constraints on growing the JianMu. And so, in order for Yaocao to ripen at the end of the segment, it has to have no more than a certain amount of nutrients. Otherwise, the nutrients can't get up that branch. So here, we've got a 380 limit on nutrients if we used 160 up here. And this next segment used 180, and the next segment used 120. Then overall we've used, we've got a requirement of 460 nutrients on this branch that's greater than the limit, and so, we're never going to grow a Yaocao at the end of this branch. Similarly, there's a requirement on leaves. So, in every window, so in the last eight segments for every window of eight segments of branches, we need a minimum number of leaves in this case 140. So in this case, this set of eight segments has got 144 leaves, and so that satisfies this leave constraint. And so there is a possibility that we can grow some Yaocao at the end of this branch. But if we have this segment here, this last segment where we only got 11 in the last step, it only has 135 leaves. It doesn't make this minimum and so there's no chance we'll grow a Yaocao at the end of this branch. And of course, the idea is to grow the strongest Yaocao, which is the most the leaves on the branch all the way up to the end. So, that's going to give us the strongest Yaocao herb. And of course, some of these leaves will not grow any Yaocao, some of these branches. Okay. So, the YaoCao problem is growing the JianMu. Each branch is having 100 segments, and each potion is required for growing a specific segment of the branch. So, we're going to apply those potions one after the other. And the potions have different characteristics. So, they grow a different number of branch segments, and in each grown segment can have a specific number of leaves, and a specific nutrient quantity required to grow it. And of course the idea is we have to get a YaoCao the end. We have to satisfy this total nutrient constraint that we don't use too much nutrients, on the whole branch and we have leaves in every window of some size, we have to have enough leaves, so that the YaoCao will grow at the end. And our objective is to build a branch which has the most leaves because that's going to give us the strongest YaoCao at the end. So, a MiniZinc model to do this, so we have a number of potions. We have a window size for this leaf constraint and the number of leaves that we need in each leaf in each window of segments, and we have the capacity of nutrients that we have available and the maximum capacity we can use, and we have the maximum number of segments which any potion will allow, that's m. And then we have the data about each of the potions. So, each potion will have for each segment how much nutrients it requires, and for each potion for each segment it grows, how many leaves will be on that part of the segment. And let's have a look at some small data. So here, we have four potions with at most four segments. The window is two, so we need at least eight leaves in every stretch of two branches. And then we've got our data for the nutrients and leaves and basically, you can see potion one has four possibilities, needing four, two, three and seven nutrients. Potion two only has two actual possibilities, three and eight, and we'll use 20 which is sort of bigger than the nutrient capacity to basically rule out the possibility of ever choosing these branches since they don't really exist. And then the leaves, so you have different leave values for different things and we use zero leaves for the non-existent segments. Okay. Our decisions of course are for each potion, we're going to choose which segment to follow to get to the strongest Yaocao. We've got some auxiliary variables here which are just recording basically for each potion for the segment we chose, how much nutrients that segment required, and for each potion, for the segment we chose, how many leaves are on that segment? And then of course the total nutrients is just the sum of these things and the total leaves just the sum of the leave lists. And now, the constraints. So, the total nutrient has to be less than or equal to capacity. So, that means by the time we reach the end, we haven't used more than the capacity of the nutrient. And then, the leaves for the window constraint. So basically, we're looking at every chunk of segments of length w along the branch and basically checking that if we sum up the amount of leaves in that segment of length w, we get greater and equal to p which is this minimum leaf requirement. And then, we've got a solving in those. We are solving, we're going to choose to solve using the leave list variable so we're going to make decisions on the leave list variables which are these auxiliary variables rather than the actual choices that we're making, that will become clear later why we do that. Okay. So, this is an optimization problem. How is it going to be solved by a constraint programming solver? In fact, it's incredibly naive. Basically, it's just going to solve a series of satisfaction problems. So basically, find a solution then add a constraint that says find me a better solution, and that's all it's going to do. And we'll basically want to help the solver by programming our search to find good solutions early. So, this is what we call retry optimization. So, you can think about it this way, we just look for a branch, we find a branch here which has a 19 value Yaocao. And then we'll add a constraint saying well, the total leaves have to be bigger than 19, then we'll restart the search. And basically, we do everything we did before, we will fail at this 19 now, because it doesn't satisfy that constraint and then we'll find the next solution of 22. So, I'll add a new constraint saying the total leaves have to be greater than 22. And then we'll do everything again to find the next solution. And we'll do everything again to find the next solution. Everything again to find the next solution. And since this is actually the optimal solution, we'll do everything again with this constraint. Now, the whole tree will fail. And then we know that the last thing we found was the best possible solution, and we found the optimal. So, that is not a very clever way of doing optimisation. So, we can think about it this way, it's kind of abstract version. So this is a retry optimisation, we have a set of propagators and an initial domain, so how we start off. And here, this is the objective value. We're going to record the best solution we found so far. So, first of all, we're just going to do a propagation search starting from this initial problem, and that's either going to return a solution which will be the new best solution. If it returns a false domain, then it basically means there's no solutions left which means the last solution we found had to be the best one so far. So, we can return that as the optimal. Otherwise, basically this value return by the search is a solution domain that has a one value for each variable. We can convert that into a valuation, we can add a constraint saying, "Make sure the objective takes a value bigger than it did in that last solution." We just add that into our propagators and resolve. I can see this keeps going until we find the optimal solution. And then the next time we do this propagation search, it will fail, and then we can return the optimal solution. And of course, we could use propagation search here, or we could do binary search, it doesn't really matter. But since our solver was using backtracking search anyway, it seems wasteful to do all of this search again and again and again. So we can do better than this by, at each step in our backtracking search, if we find a new solution we add the constraints in the middle of the search. So just adding this constraint sign, the objective is bigger than the best solution we found so far for the objective. So if we do that, our branch and boundary looks a bit better. So we find our first solution 19, then we immediately add that the total leaves are greater than 19, and then basically with one step more, we're going to find the next solution. Then we add a constraint to get rid of that solution and we'll keep going, we'll find the next solution, the next solution, next solution, the optimal solution, and then we'll get failure and you can see we're really only searching the entire search tree once. So this is much better than the free trial version. Although not always, we are going to remember that when we add a new constraint on the root, it could actually cut off lots of the search tree. For this particular example, it doesn't. So programming search is even more important for optimisation. When we find a good solution early, it's going to reduce the future search space. So if we can drive the search to find good solutions early it's going to help us. So let's look at a very small example, right, so here our window size is two, the leave requirement is eight, the capacity is 19 and here is our data about the potions and the segments, how many leaves they require. So let's do our search. Remember we're searching on this leave list variables which I've summarised as LL here. We're just going to pick them in order and pick the minimum value of leaves. So if we look at the first solution, we look at this variable, the minimum value is four. So that's basically make the choice, the first choice to be the third segment, that generates down to here. Then the next least value is five here, that generates there. And we look at the next variable, that's we pick four and then again we pick six the least value. So that has generated all these choices and we found a solution of 19. We add our constraint that the objective has to be greater or equal to 19, and backtrack up to here. Then we can't pick this least value, so we have to pick this nine. So we got a better solution 22. We backtrack again up to here, and we can up here, we can't pick the least value so we have to pick a different value, we pick this five which is the next least value. Then we find a new solution, we backtrack and we keep going. Alright. Let's try a different search. Now this time we're going to pick the maximum possible value which seems a bit better for our objective because what we're trying to do is maximise the number of leaves. So in the first value, we're going to pick eight, and in fact the constraints are going to force the next solution to pick five as well. Okay, then our next choice is to pick the maximum value here which is seven, and then the maximum value here which is six which gives a solution of 26, much better than the first solution we got last time. And we add that in as a constraint, we backtrack and then we immediately fail here, we backtrack further we immediately fail here, we backtrack up to here, now we can try the second possible value here which is seven, and we go down, that causes some propagation, we fail, and we try the second value here and we get a solution 28, which we know is the optimal, then we backtrack and then we fail. You can see it's a much smaller search tree to find the same optimal solution. Alright, let's do a different search strategy. So rather than picking the leaf variables in order, let's just pick where the largest leaves could be done, the same in domain max. So here we look across our, array, we see that this is the thing with the largest possible leave value which is nine so we're going to set it to nine. Once we do that, that fixes some other decisions, then we're going to pick one of these sevens. So here we will pick the first one and set the leave value to seven in the first decision, and then we pick the other seven. And in fact, we found a solution of size 28, we backtrack and we immediately fail, backtrack, we immediately fail, we backtrack, we immediately fail and really we've got the best of possible worlds, we've gone straight to the optimal solution and we've had to do nothing else. So, we can look at this little chart where we compare these three different variable orders of import order, largest and smallest, and two different value orders in domain Max and in domain Min. And you can see basically, the number of solutions we find which isn't that really important, the number failures in the search which is sort of a measure of how much search we did and the number of nodes we visited. And you can see it's very clear that in domain Max, whether we use largest or the smallest was the best in terms of all of these measures. If we look at the original problem size, then we can actually see that this combination of largest in domain Max is clearly the best, although interestingly smallest in domain Max still does well. So it has really shown you that actually it's in domain Max which is the critical thing that's going on here. And notice for some of these problems we couldn't prove optimality within 15 minutes. So we don't know how many fails and nodes there are in the whole tree. So, we can do more complicated searches than just here. So up to now, we've been searching on for one array of variables. We can also decide sort of one subproblem first, and then another. And this is done with this sequential search annotation where we have basically a list of search annotations inside this. So it says, first you perform search one until all the variables in search one are fixed and then perform search two to fix some more variables. So, some simple examples of using this is we are going to search over here here is leaf list search just like we've done before and then after we finish that we can try to maximise the total number of leaves. Right? So that's fairly redundant because actually once we finished, fixed all these leave list, the total leaves will be fixed, so this is really going to do very much. But we can try the other way around. So we can try to first maximise the total number of leaves without making any decisions about the actual leaves, leaf list choices, and then we can actually do the search. So it's basically trying to fix it to get a very high leaf value and then seeing if we can do that. And you see if we do this, the first solution we find is the optimal, basically we're forcing it to be optimal, actually takes us a few more fails and a few more nodes, so it's not that worthwhile in this particular example and particularly not worthwhile if we had a better version of picking the leaf list. So in summary, optimisation in constraint programming is incredibly naive. Basically find a solution, and then when you've done that, add a constraint so you find a better solution. We need to use programs search to help this by basically driving the search to places where we find good solutions early. And we can do more complicated search, sequential search for example, where we concentrate on the first important decisions first, right? That's the first thing in our sequential search and then we'll do the next variables after that and so of course these important variables are depend on the problem. So which variables most important depend on the problem and sometimes the objective is the most important thing or sometimes the choice is the most important thing or maybe there's multiple choices and doing this in the right order can make a big difference on how much search and how big a tree we have to look at to find an optimal solution.
