How to Solve an Assignment Problem Using the Hungarian Method

Aug 15, 2023

How to Solve an Assignment Problem Using the Hungarian Method

In this lesson we learn what is an assignment problem and how we can solve it using the Hungarian method.

Content

0.03 -> Hello everyone! this is Mirzaei from Cal

2.52 -> Poly Pomona and in this lesson we are

4.38 -> going to cover the assignment problem

6.839 -> and Hungarian method to solve the

9.12 -> assignment problem. What is the

10.8 -> assignment problem? A special class of

13.769 -> transportation problems is called

15.619 -> assignment problem that has three

18.09 -> especial conditions. If you are not

20.16 -> familiar with the transportation problem

22.08 -> please refer to the video related to the

24.93 -> transportation problems. So, the first

27.75 -> difference of transportation problems and

29.609 -> assignment problems is that the supply

31.289 -> and demand are the same and they are

33.719 -> equal to one. In the context of

36.8 -> operations research I, we just deal

39.93 -> with the square matrices when later on

42.84 -> we introduced non-squared matrices and

46.23 -> conditions. So, for now, we are just

48.84 -> focused on the cases that you have a

50.91 -> squared matrix for assignments. The

54.69 -> second difference between the assignment

56.37 -> problem and the transportation problem is

58.079 -> that all the decision variables in this

60.51 -> case are binary variables, meaning that

63.359 -> they only take the value of 0 or 1. If

66.09 -> you remember, you didn't have this

67.71 -> condition in the transportation problem

69.689 -> and your X's where real numbers. The

73.26 -> third condition is that all the

75.21 -> constraints are in the form of equations,

77.67 -> in your transportation problem for the

80.7 -> supply constraints you had less than or

82.86 -> equal and for a demand constraints you

84.57 -> had greater than or equal signs. But in

86.759 -> this case, all the constraints are going

88.979 -> to be in the form of equal sign. So these

91.439 -> are the three main differences between

94.14 -> the transportation and assignment

96.09 -> problems. let's look at one example and

101.04 -> see how we formulate an assignment

102.99 -> problem and then and after that we

104.88 -> explain the Hungarian method. So, in a

108.39 -> construction site there are four cranes

110.25 -> each crane must be allocated to a job

113.07 -> and the time required to set up each crane

115.74 -> for each job is shown in the table, here.

118.59 -> The question is: find the best assignment

121.259 -> of cranes to jobs so that total time

123.63 -> required for completing the jobs is

125.939 -> minimized. So, basically we want to find

128.7 -> so, basically we want to allocate exactly

131.129 -> one crane to each job and each job must

133.53 -> be

133.83 -> exactly allocated to one crane, not more,

135.96 -> and we want to do it in a way that our

139.53 -> total cost is minimized. So, in this case

143.04 -> our decision variables are binary,

145.68 -> because we're trying to decide whether

147.93 -> to allocate a crane to a job or not. So,

150.54 -> if I define all the decision variables

152.55 -> here, which are 16 decision variables, I'm

155.25 -> trying to understand whether the value

157.86 -> should be 1 [or zero]. If it's 1 then it means that

160.35 -> I make the allocation; otherwise I don't

162.36 -> make that allocation and your X

164.31 -> takes the value of 0. So, for example, if X11

167.22 -> is the allocation that I try to do,

169.77 -> allocating crane 1 to job 1 takes the

172.38 -> value of 1, it's gonna cost me 16 bucks.

175.05 -> So, therefore, I have to pay 16 bucks for

178.77 -> allocation of crane 1 to the job site 1.

182.85 -> So, if I want to define my total

185.55 -> objective function, I can define it in

187.95 -> here, [by] asically multiplying the cost

191.79 -> coefficient to each decision variable

193.59 -> and if the decision variable takes the

195.42 -> value of 1 then the costs associated

197.37 -> with that gets activated. In the end, we

200.22 -> just want four of these decision variable to

202.53 -> become 1; because for each crane and

205.05 -> each job exactly we want one allocation.

207.81 -> So, we have to make sure that for each

210.03 -> row we only have one decision variable

213.06 -> that is equal to 1. So, I write the

214.98 -> constraints regarding the cranes.

217.41 -> So, for each crane we want to exactly

219.39 -> allocate it to one job site. For crane 1

221.82 -> 2 3 & 4. Also, for each job I have to make

225.72 -> sure that I'm not allocating it to more

227.55 -> than one crane. So, for each column also I

230.88 -> have to write one equation and enforce

233.82 -> that one of those X's in each column

236.4 -> becomes 1. You can think about it like a

238.739 -> Sudoku game. So, you're trying to put 4 ones

241.83 -> in this table so that each row’s and each

243.959 -> column’s summation is exactly equal

246.39 -> to 1, and also you have to mention in the

249.03 -> end that all the X's are binary. If you

251.549 -> make that allocation the X is 1;

253.23 -> otherwise is 0. Now, how we can solve this

256.979 -> problem? Since all the X's are binary

260.13 -> variables, we haven't covered a method

262.049 -> so far that you can solve this problem.

264.26 -> One method to solve this problem is

266.85 -> called Hungarian

267.389 -> method. Let's learn Hungarian method

269.49 -> using an example. This is a table of the

272.819 -> cost for crane - job allocation. This is

275.699 -> not similar to the one that you saw

277.68 -> earlier. This is a different example for

279.629 -> certain reasons. So suppose that you're

282.689 -> trying to find the best allocation of

284.4 -> cranes to jobs and numbers inside the

288.15 -> table are the time that take for you to

289.949 -> do this setup and therefore you are

292.02 -> trying to minimize the set-up time. So,

294.33 -> it's a minimization problem. The way that

297.06 -> Hungarian method works is first by

299.819 -> finding the minimum of each row and

302.159 -> subtracting it from the values in that

305.37 -> row. So, first, let's find the minimum of

307.529 -> each row. As shown on the screen the

309.96 -> first row minimum is 2, the second row is

312.15 -> 3, third row is 4, and the fourth row is 3.

316.319 -> Now we subtract these minimum value from

320.49 -> all the rows and we get to this new

324.779 -> table. The next step is to find the

328.169 -> minimum of each column and then subtract

330.87 -> that minimum from each column. So, for

334.8 -> each column I wrote the minimum value

337.289 -> and now subtract that minimum from each

339.839 -> column in the next table and this is

342.509 -> what I get. So, so far, what we did we

345.36 -> found the minimum of each row and

347.819 -> subtracted from their

350.039 -> associated row. Then, we found the minimum

352.71 -> of each column and subtracted that value

355.169 -> from each column. The third step is to

357.779 -> find a minimum number of vertical or

360.99 -> horizontal lines that we need to cover

363.779 -> all the zeros in the matrix. The way that

367.379 -> you lay out those lines does not matter.

370.439 -> The most important thing is to use the

373.08 -> minimum number of lines to cover those

376.05 -> zeros and your lines cannot be diagonal,

378.3 -> it should be vertical or horizontal. So,

381.419 -> the way that I lay out my lines is

384.3 -> this way. But you can choose an

386.219 -> alternative way. But you have to make

387.899 -> sure that you are using the minimum

389.52 -> number of lines required. I'm going to

391.68 -> take this to the next slide and continue

393.599 -> here. So this is what we have gotten so

396.419 -> far. Now what? So, if the minimum number

401.34 -> of lines required to cover all the zero

403.26 -> is not equal to the dimension of your

405.69 -> matrix, which is four, then you haven't

408.69 -> reached the optimal allocation yet.

411.99 -> The dimension of your matrix is four

413.49 -> by four. So, your m, representing your

416.37 -> dimension is four. So the minimum number

419.37 -> of lines is three. What you need to

421.74 -> do is to go to the next step. If the

424.95 -> minimum number of lines was equal to four

426.93 -> then you had reached the optimal

428.58 -> solution and each zero would show you

431.34 -> a possible allocation. But since we

433.92 -> haven't reached to that point, we'd

435.24 -> continue to the next step and this is

437.46 -> that we have to find the minimum of

439.5 -> uncovered value and then subtract that

441.96 -> minimum from all the uncovered value and

444.78 -> add it to the corner points and from

447.72 -> corner points I mean the intersection

450.15 -> points, wherever your lines are

451.74 -> intersecting. So, if I do this step I find

455.76 -> the minimum of uncovered values in this

457.86 -> case is 3. I subtract that from all

461.52 -> the uncovered values, which are the values

466.14 -> that in the next table you see

467.79 -> by kind of dark brown and now I have to

472.02 -> add it to the corner points or

474.03 -> intersection points, which are 6 and

476.37 -> 1. So, if I add 3 to those

478.14 -> intersection points I get 9 and 4

480.3 -> the rest of the points are remained

482.61 -> untouched. I don't do anything with the

485.19 -> rest of the values and copy them as they

488.64 -> are in the new table. So, find a minimum

491.04 -> of uncovered value adding them to the

493.59 -> corner points and subtracting them from

496.11 -> the uncovered value. So that's the step

497.88 -> that we implemented. Now, we go back to

500.13 -> the third step, try to find the minimum

502.59 -> number of lines that we need to cover

504.96 -> all the zeros. In this case again with

507.6 -> 3 lines I can cover all the zeros. So,

510.24 -> 3 is not equal to 4. So, I have to

512.64 -> continue and redo this step number four.

516.47 -> So we went back to the step 3, 3

519.69 -> is not equal to 4. We go back, I'm

522.03 -> taking this to a new slide and as you

525.39 -> saw this is the final table we had. Now I

528.33 -> have to find the minimum of uncovered

530.43 -> value, which is equal to 1, subtract it

533.22 -> from uncovered values,

535.17 -> added to the intersection points and copy the

537.93 -> rest of the table as they are. So, I'm

540.06 -> implementing these a steps. I deduct 1

543.51 -> from all their uncovered value, added to

546.45 -> the intersection points, and copy the

548.34 -> rest of the table as they are. Now, I have

550.83 -> to find the minimum number of lines I

552.78 -> need to cover all the zeros. In this case,

555.3 -> I need at least 4 lines to cover all

558.93 -> the zeros. Therefore, 4 is equal to the

562.11 -> dimension of my matrix which was four

564.57 -> and therefore I'm in the final optimal

568.02 -> table of assignment problem. Now, how I

570.69 -> make the assignment. Each zero in the

573.09 -> final table shows a possible allocation.

576.05 -> But you have to be very careful with the way

578.85 -> that you make these allocations. For

580.8 -> example, if I choose this allocation, it

582.72 -> means that crane 4 cannot be allocated

584.51 -> to job 2 anymore. So, I have to make sure

587.79 -> I pick the zeros in a way that each job

590.55 -> and each crane has exactly one

592.56 -> allocation. So, one systematic way to find

596.64 -> the allocations using the zeros that are

599.37 -> in the final table is to start the

602.01 -> assignment from the row or column that

603.87 -> has the minimum number of 0s. Because

606.48 -> those are the one with the lowest option.

608.85 -> So, the way that I deal with this is [that] I

611.64 -> start writing the number of

614.1 -> zeros in each row and each column. For example,

616.11 -> in the first row I have two zeros and

619.5 -> the second row I have two zeros and in

621.9 -> the last row, for example, I have three

623.55 -> zeros. Then I start allocation by

625.52 -> allocating the row and column that has

628.65 -> the lowest number of possible options. So,

631.95 -> a lot of rows and columns have two

634.17 -> options. So, you can pick one arbitrary.

636.93 -> What I pick is the first allocation of

639.96 -> crane 1 to job 1. With this, I cannot put

643.11 -> any other allocation in this row or column.

645.06 -> Therefore, I eliminate them and I

647.01 -> have to also update the number of zeros

649.74 -> in the remaining table. Now there are two

652.44 -> numbers that are updated because this

654.75 -> zeros are eliminated from the table. Now

658.26 -> everything has two options. So, I pick

660.81 -> another one and randomly and make the

663.18 -> allocation and eliminate the row and

665.25 -> column related to that allocation.

667.95 -> Now, I have to update the number of zeros in

670.14 -> each row and each column. Now as you see

672.48 -> there is a row and column with only one

674.79 -> possible allocation. So, I picked this

677.79 -> column because it only has one

679.35 -> allocation. I make the allocation there,

681.63 -> and then eliminate that, and I'm left

684.09 -> with only this allocation. So, this becomes

686.28 -> the final allocation of cranes to jobs.

689.58 -> Now, this is the final solution that we

692.1 -> found our final solution is X11, X21

695.37 -> X34 and X43 have a value of 1 and

700.86 -> therefore the costs associated with

703.08 -> these are going to be activated in my

705.24 -> objective function. If I go back to the

708.42 -> original cost table I have, I can pick

711.24 -> the cost associated with those

712.68 -> allocation and calculate my final

715.35 -> objective function value. So, as you see

718.53 -> my final objective function value in

720.54 -> this case is equal to 19 by finding the

723.69 -> cost associated with those allocations

725.94 -> that I've made in this case. With this

730.11 -> our lesson regarding assignment problem

733.08 -> and Hungarian method has concluded thank

735.63 -> you for watching!

Source: https://www.youtube.com/watch?v=ezSx8OyBZVc