Method used to solve assignment problems

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics.

Each applicant gets one job.

• Find a maximum matching (give jobs to as many men as possible) for which the sum of the cost of the edges is minimized

In the previous lecture, we have learned:

The assignment problem can be formulated as a 0,1-integer linear constrained optimization problem (i.e.: IP)

jobs -------------> 1 2 3 +- -+ 1 | 1 4 5 | C = 2 | 5 7 6 | 3 | 5 8 8 | +- -+

min: 1x11 + 4x12 + 5x13 + 5x21 + 7x22 + 6x23 + 5x31 + 8x32 + 8x33 s.t.: x11 + x12 + x13 = 1 // Worker 1 gets 1 job x21 + x22 + x23 = 1 x31 + x32 + x33 = 1 x11 + x21 + x31 = 1 // Job 1 assigned to 1 worker x12 + x22 + x32 = 1 x13 + x23 + x33 = 1 xij = 0, or 1

• IP Prog file: click here

Value of objective function: 15.00 Actual values of the variables: x11 0 x12 1 x13 0 x21 0 x22 0 x23 1 x31 1 x32 0 x33 0

We can solve a Linear Program instead of an integer program --- this is due to a special property

It will only produce integer solutions

The Simplex Algorithm is a general purpose algorithm to find the maximum/minimum of a linear cost function with linear constraints

We can exploit the structure to improve the performance of the Simplex Algorithm for some special type of problem.

The Network Simplex Method is a (primal) Simplex Method adapted to solve the maximum flow problem in networks

The Hungarian is a (primal-dual) Simplex Method adapted to solve the assignment problem in bi-partite graphs