Our next type is the assignment problem, so this seems to be very similar to transportation. But still, there are some difference let's say there is a manager. This manager is assigning on jobs to workers. Okay, so you have jobs here and you have workers here workers, okay. And then the assignment must be one to one so that means one job can only be assigned to one worker, and one worker can only do one job. You cannot split a job, the cost for workers j to complete job I is called CIJ. Okay, so it's here and of course, we want to minimize the total cost okay. So obviously, this is a special case for the transportation problem. Jobs are cold factories in the previous problems setting and the workers previously cold markets. Now it's just that each factory produced exactly one item, and each market demands exactly one item. So when you say there is an assignment, that's exactly equivalent to shipping one unit from here to there. All right, so this is nothing but in assignment, problem or nothing but a special type of transportation problem. Maybe you would want to ask yourself what's going to happen if the number of jobs is fewer than the number of workers okay, so you have several workers. You don't need to let all the workers to have jobs, but you need to complete all the jobs. Well, if that's the case, formulation wise is just the same. But actually, you need to deal with this problem if you want to formulate this as a transportation problem, okay? So if you want to formulate that as a transportation problem, well, that's not a very big problem. Because all you need to do is to create a virtual supply or a virtual job or several virtual jobs. So that the delivery from virtual jobs to all your real workers has a cost of zero. Okay, so for example, suppose you have workers zero this is a real one, and you are going to create another virtual job. And in that case, all you need to do is to say, okay, this is a cost zero cost, zero cost zero for and so on and so on. Pretty much you somehow just have this virtual job to make It satisfies the requirements for transportation for assignment. Okay, the second problem requires you to have equal number of jobs and the workers, so you create these virtual job now to satisfy these requirements. So that's right to take a look at i p formulation for transportation and for assignment, we're going to say I is the set of factories or jobs J is the set of markets or workers. So in that case, we're going to see, given our decision variables X i j in transportation problem, we may set it to be integers. Given the transportation quantities, this is our total cost and here for each for each node I where node i means of factory for each factory i. The total shipping quality out from that node i should be the total supply quality for each market J the total amount shift in should be equal to the demand quantity. Okay, that's transportation for assignment is simply first, your N becomes because now you have N jobs and N workers and the second, all your quantities are one. Okay, because now one person works on one job, one job is assigned to one person, and finally, all your decisions will become 01. So here you actually don't need to set it to 01 If you set two integers, it will still be 01 there's no way for you to have 23 or five. Okay, so that's one thing also, please take a look at this statement. It says that if you take a look at this, coefficient matrix is obviously they should also be total unit modular, totally unique modular. So we may put roles for I in one group and the roles in J to another group then you will have this total unit modularity. And finally, in typical cases, we don't want those integer variables we will use fractional variables to deal with them. But you may know that if you focus on this interior constraint for assignment problem, which is actually a binary constraint if you relax it, then by nature, you are allowing jobs to be split. You are allowing one person to work on multiple jobs, this violates your original setting. Okay, so that's why I would say relaxing the interior constraint for the assignment problem is a critical thing. If you relax that if you want to say your XIJ can be zero or one or any number within zero or one, you need to make sure that this is not going to have a job split. This is not going to make a solution that really violates your constraints okay, luckily, we know we can do that. We can really relax that constraint, because we have total unimodularity. So the last thing I want to introduce in this video is the transhipment problem. If there are transhipment notes in the transportation problem, that is called a transhipment problem. So I'm going to skip the formulation here I just want to show you that in general, MCNF formulation can be Look at this right and pretty much we have a relationship here. An assignment problem is a special case of transportation problem in a sense that for an assignment problem all your b i. Are one or negative one transportation problem is a special type of transhipment problem in the case that none of your b I is zero. And finally, a transshipment problem is a special type of MCNF in the sense that there is no link capacity constraints. All right, so we can see that we have this clear reduction map or reduction relationship
