Assignment problem example in operations research
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
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
