Having solved the tunnel problem Liu Bei gained more trust from Cao Cao and was subsequently ordered to suppress a small rebellion that had broken out. Guan Yu accompanied Liu Bei to the battlefield and his right arm was severely wounded whilst fighting against the rebels. Liu Bei took Guan Yu to see Hua Tuo, the most famous doctor at the time, for treatment. After thoroughly assessing the wound, Hua Tuo proposed to heal it using acupuncture therapy, targeting ten different acupuncture points. The therapy involved four stages, each of which included jabbing three particular acupuncture points according to some special requirements. These were one, none of the same points could be jabbed more than twice across the four stages. Two, within each stage, the closer the point was to the head, the earlier the point could be jabbed. Three, for any two consecutive stages, the first point to jab in a latter stage, needed to be further from head than in the former stage. And the same requirements apply to the second and third points. Additionally, Zhiyang and Zhongshu were two important points that could only be targeted once during the entire therapy. Aware of these requirements, Hua Tuo thought it would take him quite a while to figure out a treatment plan. However, Guan Yu's wound was quickly getting worse. Liu Bei offered to use the magical tablet to determine an appropriate course of action more quickly. So Hua Tuo is going to use acupuncture to fix Guan Yu's injuries. So the acupuncture treatment is going to be using needles down the spine. It's a complicated treatment and it has complicated rules. So it's going to be a four stage treatment and in each stage, he's going to put three needles into the spine of Guan Yu. And the needles are going to move down the spine, each one further away from the head in each step. So there's a specification that you can't hit the same spot in the spine three times. So that's not allowed, you can't have any treatment pattern where we hit the same spot three times, that would be too dangerous. And we have this ordering constraints, where every needle is got to move down further away from the head in every treatment step in order for it to be successful. And finally there are some very delicate points of the spine which can only be hit once during the entire treatment. So this is the acupuncture problem that we're going to solve. So let's look at the problem data we have an enumerated type which is giving us the acupuncture points, the number of jabs or needles that we're going to use in each stage, and the number of stages in the treatment plan. Now here's the Declarations that we're going to use. Which obviously match the data that we just saw in the previous slide. Now let's look at how we're going to build our model. So there's a set viewpoint where we're going to say, well in each stage, we have to think about the set of needle positions that we're going to pick. So, here's our decision variables at each stage, the set of spots that we're going to place a needle in. And of course, there's a cardinality of c, we're going to hit exactly three, the cardinality of c, in that set. So this is a set viewpoint, now we want to make sure that we have none of these triples intersects. If we take any three of these sets, they don't have an intersection. So that's easy enough to write down, we just take each i, j, k which are different and we look at the intersection of stage i with stage j with stage k, it should be empty. That makes sure that in any three sets, if we look at their intersection it's empty, which means that no spot can be done, can appear in three different stages. Now we need that some of these delicate points appeared exactly once. So we can just sum up the number of times that this thing appeared and say it's less or equal to one. Sum up the number of times this appeared and say it's less or equal to one. But how do we represent this ordering constraint? That every needle effectively moves down the spine. It's very hard to represent that ordering constraint using the set viewpoint. So let's look at another viewpoint for representing the same model. So we've seen in the past how we can represent a fixed cardinality set using an array. So here for each stage, we're going to have an array of size 1 to c of the spots that we hit. And of course, we're going to order those arrays. We'll just order them in increasing order to get rid of the symmetry, that we can have multiple ways of representing the same set by just reordering the same points at the same stage. And now, it's easy to order the fact that every point, every needle moves down, away from the head in every stage. We just say that the ith needle, in the ith stage, the jth needle moves to a position which is greater in the i+1 stage. So we can also express the case that some points are only hit once by using global cardinality constraint. We can just count basically in these whole points [i,j] matrix, how many times we saw these two delicate points and it should be between zero and one. Using global cardinality low up where we're just giving the lower and upper bounds on the number of times that we saw those. But it's hard to represent the intersection in this case. How do we talk about three sets and their intersection? So that means that we have a different kind of multiple modelling that we could talk about here, which is we can channel these two representations. So before, when we were multiple modelling, we had two different viewpoints and we were channeling between those two different viewpoints. Now we really only have one viewpoint, we're picking a set, at each stage, but we have two different representations of the same set. And we need to channel between those two different representations. So here we have our two different representations of our fixed cardinality set. We have this var set of objects with a cardinality constraint and we have our array of size 1 to u of objects and some constraints getting rid of symmetries let's say, saying that those objects are in decreasing order. Now, what's the channelling constraint going to do? Well, we're going to have to say for every object, if it's in the set s, then there has to be some position from 1 to u in this array, which takes that value o. That to make sure that this object o appears in the array representation of the set. So that's channeling in one direction that's forcing if it's in the set, then it's in the array representation. We also need to channel the other way and that's saying just much easier, we say, for every one to u, x of i is in the set. So every element which appears in the array also appears in the set. So we with those two constraints we're making sure that this two different viewpoints on this set that we're building up agree with each other. Once we've done that, then we can build our model with those both of those viewpoints. So the channel for our acupuncture problem is of course a little bit more complicated because we've got an array of these sets. But basically it's exactly what we're seeing here. For each stage i variable, we kind of say that there's some j where the point of [i, j] takes the values in that set. And we're saying that every point of [i, j] is in the set s [i] and we can add to that the constraints. We can use non-intersection from the stage variables, we can use ordering from the point variables, and we can use only-once from either viewpoint. And so we've build our combined model here using two different representations of the same viewpoint and building our constraints with whichever representation was more convenient. So in fact we could represent the intersection constraint using the array model. So our constraint that the intersection of any three stages had to be empty is really the same as saying no element appears more than twice. So really this is a kind of counting problem and we can use a global cardinality constraint to do that. So we can use a global_cardinality_low_up_closed constraint to count. We just count all of the things that occur in the points [i,j] across all of the stages. And for each particular value we want that there's a lower bound of 0 which is basically no lower bound and an upper bound of 2. That's going to force that we don't see any point used more than twice in the entire model. So in that case we can get away with just one viewpoint, just the point array, and not have to use the second viewpoint for this particular problem. So for this particular problem we could get away with a single way of representing our viewpoint. But if we changed it slightly it would be very difficult. So if we take this version of the non-intersection constraints saying that the intersection of any three sets can be at most one. So that's if we take any three stages, there can only be one point in common in those three stages. And that's very straightforward to write down using the stage variables, but it's very difficult to see how to do that using the point variables. So, there are certainly examples where we need two different representations of the same decisions just to be able to write down the constraints efficiently. And then we need to make sure that those two different representations of the decisions also agree using channeling. So we go back to our Yellow Turban problem and we can also think about channeling unbounded separate representations. So in the Yellow Turban problem we had an array of var 0..1 decisions which things we were going to choose and we could also represent this is a var set of objects s. So we can channel those by saying, every o in the objects s of i equals o in s. So basically, this Boolean is true if the object is in s as the same way. So, is there an advantage of this kind of channeling? So we'll leave that question up to you to explore. So in summary, channeling we also can apply to different representations of the same viewpoint. And again, what we're doing with this channeling or multiple viewpoint approach, is to take the best variable representation over decision for a different constraint or different part of the objective. And combining models allows us to use that best representation for each constraint or the objective. And then we only have to insure that the multiple representations agree. And this is very worthwhile if there is a difference in solving for the representations is large. So, if we can use a global constraint, for example, in one of the representations it's likely that some solvers will take big advantage of that, to be able to solve it very effectively. And, of course, we have to pay the cost of having two representations. So if we have to pay a very large cost to make those two representations agree, then it's not going to be worthwhile. So we have to take that into account as well. So multiple modelling is a powerful tool in the modeller's toolkit. Which will allow us to solve problems that can't be solved otherwise because it allows us to get the best representation of each of the constraints, even if they're not necessarily the same in our model. So remember, modelling is an art and the only way to get good is practice. And I hope over these courses, you'll get plenty of opportunity to do lots of practice in modelling. And that will get you to understand some of these trade offs that you come to in multi modelling and choosing representations, etc.. So in future lectures we'll investigate things like more model combination, how that affects efficiency. And in particular we'll look at for constraint programming based solvers, how global constraints like inverts work, and how they'll help you in your model combination.
