Some enemy soldiers, along with their families, were captured during the war. The coalition plans to put them into prison cells in a grid, according to some rules. No two prisoners could be put into the same cell. Some prisoners were so dangerous that no prisoners could be put in any of the adjacent cells. Female prisoners could be put in the cells of the upper half of the grid, while male prisoners could be put in cells at the lower half. Each cell had a different maintenance cost, and the coalition needed to allocate the prisoners to the cells so that the total maintenance cost was minimized. Once again, Liu Bei called for help. So Liu Bei has been successful on the field of battle but victory does not come without it's costs. He's collected a lot of prisoners of war that he has to deal with. So he has to put these prisoners of was in cells, giving him a CellBlock problem. So of course the first thing is that he's got, he can't put two prisoners in the same cell, that would obviously lead to collusions and escapes and all kinds of other problems. So the next thing is that some of the prisoners are quite dangerous in fact. And if they were put into a cell then if there's anyone next to them, then they'll fight them, drag them, kill them, whatever. And that will defeat the purpose of trying to keep the prisoners alive. So, you can't put anyone in a cell next to a dangerous prisoner. So also in order to keep peace within the prison he needs to separate the males and the females. And so he's going to keep the female prisoners in the top half of the prison and the male prisoners in the bottom half of the prison. And finally there's a cost for each of these cells because they are serviced by different people and different costs to get the various things, so each cell has a different cost to service. And obviously, in the game of war, it's all about minimizing your costs so you can keep your army going for as long as possible. So here's our CellBlock model, we've got an enumerated type, which is the set of prisoners and then we've got a CellBlock, which is a set of rows and columns. And then the basic data of that for each cell in the block, row and column, how much does it cost to put a prisoner in that cell. Now, in our prisoners we've got set of dangers prisoners and a set of female prisoners. And then we got the male prisoners, those are different from the female prisoners. So now we got a dependent parameter declaration. So here, we could actually use not define males, we just use this definition instead. But it's much more natural to actually define this macro male effectively so we keep track of who are female and who are male, it'll come out much clearer in our model, what's going on. So what are our CellBlock decisions? Well, we've got to think about this. It may not look like this in an assignment solve problem, but it is. We've got our prisoners are the domains of the function that we're trying to find, and the object of the codomain are the row times column, it's the cell blocks. But we're not going to represent this as a single function, we're going to break it down into two functions because that's a much more natural way of representing the problem. So for each prisoner, we're going to really decide two functions. That is, which row is that prisoner in and which column is that prisoner in? Of course those two functions together decide which exact cell they're in. That's because it's going to be much more natural to reason about and express some of the constraints of the problem with these two functions than with a single function, which only names an exact cell position. And these are the kind of decisions that we need to make when modelling. What's the right way of representing what we're doing in order to make it easy to express the constraints and the objectives of the model, in order that the solver can solve it efficiently. So we can think about how we gotta express the constraints of the problem. So no two prisoners in the same cell. So one way to do this is to look at each pair of prisoners, and we'll say, well we've got to make them not in the same cell. Well one way of doing that is saying the absolute value of the distances in the rows, and the distances in the columns, if we add them up, has to be greater than 0. So that means that we can't have them in both the same row and both the same column, so that's one efficient way of writing that down. Can't we use alldifferent? Remember this was an assignment subproblem and what we would like to say is capture that substructure had use the alldifferent constraint. So that as solvers you can make use of that and get the maximum value out of it. Yes we can and in fact they're much better way than doing this is to map this to an alldifferent. But in order to do that, we're going to have to create, basically, a unique number for each CellBlock, which is easy enough to do. We take the row number, we multiply it by the number of columns there are and add the column number and that's going to give us a unique number for each cell. And then we're going to force those to the alldifferent for each prisoner and that will force that each prisoner is in a different cell. And then we've now used our global constraint, all different to make sure they're all mapped to a different cell. So this is where if we had a model which only gave a unique cell number, this would be very, very convenient but it would make the rest of the model much more difficult. And so we only need it for this thing, let's only create this view of the problem for the alldifferent constraint and nowhere else. Now, we have to have no adjacent prisoners in here the kind of model we used up here is very efficient. We're going to say that if we take the absolute value of the rows and the columns, they have to be greater than one which will make sure the distance away is at least more than one. So, we can't be right next to the cell of a dangerous prisoner. So, we look for each prisoner and for each dangerous prisoner where it's not the same obviously the dangerous prisoner can't be the same cells themselves or herself and so, for each other prisoner that can't be within a distance of one. If we go in this horizontal distance. So that will effectively map that we're far enough away from the dangerous prisoners. And then we can't use a combination such as the alldifferent, a more complicated constraint meaning to express it in a more complicated way. For the gender constraints, we're saying for each of the female prisoners, the row number is (n + 1) div 2. So we just saying it's in the top of the prisoners prison and the male prisoners are n div 2 + 1, so they're in the bottom half. And note we're using male here which is clear in their placing with the definition. If we just had prisoner diff female here, wouldn't be so clear what we were doing. And finally the objective function of course, what we're looking as for each prisoner, we're just looking up the cost of the cell that we placed them in and adding that up. That's the total cost, and we're minimizing the cost and so there is our CellBlock model completed. And if run it, we're going to find a solution where we put our female and male prisoners in different places and we get a Total Cost. So I hope you see that this is an assignment subproblem. Even though if we looked at it first sight it looked like even our row and column variables, we didn't really see that we were building a single function, right? We built two functions but they still have an assignment subproblems and subsection. And we could still make use of the alldifferent constraint in building our model. And indeed if we look at the next problem from Liu Bei, we'll also see assignment subproblems but this time it will be bijective and this will introduce us to matching problems.
