0:01

Welcome to the reference material section on Transforming Data.

Â So, many times when we're trying to built up a constraint

Â which represents part of the problem.

Â We'll have the information that we need to built the constraint packaged in

Â a different way than, than is natural for building constraints.

Â So, we may need to create a new data representation in order to

Â build constraints.

Â So, let's look at an example problem.

Â We've got n agents and we need to pair them up and

Â each agent has a list of preferred agents.

Â And then that can only be paired with one of their preferred agents.

Â And we need the pairing to be stable.

Â And what this means is,

Â if agent i is paired with another agent j, but prefers agent k,

Â then agent k must be paired with an agent l that they prefer to i.

Â So if that's not the case, then basically it's advantageous for i and k to join

Â each other and leave their current roommates because they'll both be happy.

Â So in the stable roommates problem, we do appear in such that there is no

Â pair that would be happier if they lived together to be in a new room.

Â So, here's an example of data.

Â So, we've got six people and here's their rankings.

Â So rank, person one prefers person two, and four, and five, in that order.

Â Person two prefers six, one, three metal.

Â Three prefers two and four, etc, etc.

Â So, I welcome you to try and generate a stable pairing.

Â 2:17

Now, we should look at this some unstable pair.

Â So if we look at the pair one and four,

Â then one is currently its third preference and this would be a second preference.

Â And four is currently there with its second preference and

Â then this could its first preference.

Â So we can pair those up, right, and if I break these two pairs here,

Â pair those up and indeed once we do that,

Â we can also extend the pairing between six and five.

Â Right, so this is a better matching because one and four,

Â we've got one less unstable pair.

Â So, we can look at this further and we'll also find another unstable pair.

Â So we look at two and six, and both each other's first preference and

Â two currently has its third preference and six has its second preference.

Â So that is another unstable pair, so we can change to that matching.

Â And we end up with three and five with no one left to pair with, but in fact,

Â there's no better matching.

Â So, this is a stable matching for this example.

Â 3:52

And given that input, we can calculate for each agent the number of preferences

Â they have by just summing up the number of times that this agent of a,

Â i is greater than zero.

Â And then we should check that our data that's in the format that we assume it is.

Â And that's saying, okay, for every i, j in the number of preferences of a,

Â we make sure that they're not the same version.

Â So we kind of have two preferences for this same a other agent, and

Â we also want that for every of the first elements in the list.

Â This agent from 1 to npref[a],

Â the agent that we're talking about here is not zero, it's a real agent.

Â If that's not the case, then the preference data for that agent is wrong.

Â So, here's our example data written this way.

Â You can see the preference array.

Â We have 2, this is the first preference for number 1, and 4 and then 5.

Â And then we're panning out with zeros until we've run out

Â of the preferences.

Â And for 2, 6 was their first preference, then 1, then 3, and

Â then no more preferences.

Â We can calculate the number of preference for each thing and obviously we get 3,

Â 3, 2, 3, 2, 3.

Â And we also check that all the zeros appear at the end because

Â basically we're going to check that from one to three in this array,

Â they're all greater than three.

Â So, what do we actually have to do for decisions?

Â Basically, we're going to have to pair each agents with another.

Â Now, some agents may not be paired, so we're going to basically assign the pair

Â of the agent as another agent or this extra agent zero.

Â 5:32

Now obviously, the pairing has to be possible.

Â That is, we can only pair an agent with someone who appears in their preferences.

Â So, we can work out the possible set of agents that an agent can be paired with by

Â basically looking on the preference list from 1 to npref.

Â So, these are the actual real preferences of the dummy zero preferences and

Â boolean at set.

Â And then we can say, well, the pair, whoever we pair a with has to be

Â in this possible set or it could be zero if a ends up not being paired.

Â The other critical constraint about the pairing is of course,

Â that pairing must agree.

Â That if we pair a with b, then we must pair b with a.

Â Now of course, if we pair a with zero, then this constraint is false, right?

Â Because pair of zero will be a, this is an out of bounds error and

Â the other half of the relation will make that false as well.

Â So, if you think about what happens when one of these pairings are zero.

Â 7:29

We'll look at three different approaches to the we can add it to the data farm.

Â So just add it as a new data, that's one way of doing it.

Â We can use constraints to build,

Â we can write constraints to force the rank [a, b].

Â They used to take the rank arrays or we can use more complex comprehensions.

Â So, adding it to the data file is fairly straightforward.

Â So here, is our two-dimensional array of agents and it's basically saying,

Â okay, agent one ranks number two as the first preference.

Â Number four as the second preference and number five, it's the third preference.

Â Agent two ranks number one as the second preference,

Â number three is the third preference and number six is the first preference.

Â So, we can see a different view of the data.

Â Now, this is advantageous and the reason is we can use any program we want

Â to create this other view of the data.

Â But when we do this we have to be very careful.

Â We have to ensure we don't have to add to our model sign.

Â It's going to check that the preference information and

Â the rank information actually agree, right?

Â So we know that if we have two agents and

Â i is in the preference set with a, and we know that the i's

Â preference of a is b means it must be that the rank a gets to b is i.

Â If that's not the case, then something has gone wrong and

Â your ranking doesn't agree for those pair of agents.

Â We also have to do something else, we have to see if a ranks b is zero, so

Â that means it has no ranking for it, then it shouldn't be the case.

Â But there's something in its number of preferences,

Â some i, the i's preference of a is b.

Â So, we have to check these things to make sure that the preference and

Â the rank array agree on the data.

Â And if we're using two views of the data that are both coming from the outside.

Â It's essential that we check the date, give us the same year.

Â So, another way of doing the rank array is to use constraints.

Â So now we have to make this a variable array,

Â because we're going to use constraints to evaluate it.

Â And then we can basically wipe down the constraints which define it.

Â So we know for two agents, if the preference and i and

Â the number of actual preferences are made,

Â then if i's preference of a is b and the rank of ab should be equal to i.

Â So basically that's exactly the definition,

Â we have to also ensure that the other ones, so this one is applied.

Â So if a and b, if there's no preference between a and b,

Â then this one forced at the rank of a, b, zero.

Â So, we have to do that as well.

Â So we're looking two agents and for none of the preferences of a there's

Â an i which gives us agent b then we're going to set the rank of a b equals zero.

Â So this can be very easy, because basically, often the relationship

Â between these two views are very simple to write down with constraints.

Â But there's strong disadvantages that, when we use this model,

Â the rank is not fixed in translation time.

Â So remember, when we gave them the data these were not variables,

Â these were just integers from zero to n-1 those ranks.

Â So, all the ranks were known at translation time.

Â So in this model, the ranks are not known.

Â So wherever we use them, we're going to be using variables.

Â And it gives it more resolve to do.

Â So another thing we can do, is we can just build the rankings and comprehension.

Â And now we have to be a bit clever about how we do that.

Â So, we know that this is a two-dimensional array for pairs of agents.

Â Now, how can we work out to put the right value i in this a,

Â b position for a pair of agents?

Â So this is the expression that's fixing a in i, and

Â we're going to sum up for i in the number of preferences of a.

Â We find that preference at the i-th position of a is is b,

Â then this will evaluate to true, and so we'll add up i.

Â 12:17

So now we've got our rank array, we can build our stability definition.

Â So remember, if agent i is paired with agent j but prefers agent k,

Â then agent k must be paired with an agent l, they prefer i.

Â So basically if i ranks k better,

Â right, than the person they're paired

Â to then either that k ranks i not at all.

Â So, k will not allow itself to be paired with i.

Â Or k ranks i worse than the person they currently paired with,

Â So that's what that constraint effectively says.

Â Okay, so you have to be a bit careful.

Â What if, so we have to make sure that if i ranks k then k doesn't rank i,

Â like in this case, that's allowed.

Â All right, so

Â we have to add that extra position, otherwise the stability might fall.

Â 13:21

So, another thing we can do here, to simplify this thing is really

Â if i ranks k, and k doesn't rank i, then they can never be paired.

Â So, we could actually build a better version of the ranking way by getting rid

Â of rankings which would never be allowed.

Â So here, what we have done is whenever we are about

Â to add an i because the I expectance of a to b.

Â So, we are about to say that the rank of a of b is i, we add this check.

Â That there is some ranking that b is to a.

Â Some position j, where b is a preference of a.

Â If that's not the case, then this whole bool2int will evaluate to false, and

Â we'll get zero.

Â So basically, it replaces rankings which don't have a paired ranking by zero.

Â 14:36

So in overview, real combinatorial problems require data.

Â And MiniZinc only has limited structures for representing data, basically,

Â those which are common.

Â So, you need to learn how to use MiniZinc to encode data of your problem and

Â to create new dependent data.

Â Because often you would want the form in a different data than you were given to

Â build a constraint the right way.

Â So, this could lead to some challenging declarative programming,

Â we cannot do all in.

Â But in the worst case, you can generate the model with the data from outsite.

Â That's something else to re-write, the data to a different form but to do that,

Â you need to add the assertions to the model to check that

Â the two views of the data you're given actually agree.

Â That's a pretty standard set.

Â