Transshipment Lpp

Applications of Maximum Flow and Minimum Cut Problems In this handout • Transshipment problem • Assignment Problem

Transshipment Problem  Given:

Directed network G=(V, E) Supply (source) nodes Si with supply amounts si, i=1,…,p Demand (sink) nodes Di with demand amounts di, i=1,…,q Total supply ≥ total demand Capacity function u: E → R  Goal: Find a feasible flow through the network 17 which 4 D 11 5 B total demand (if1 such a flow 1 satisfiesSthe 2 exists). 2 5 5  Ex.: A 2 15 5 4 19 9 S D2 8 C 2 16

Solving the Transshipment Problem via Maximum Flow 

The transshipment problem can be solved by creating and solving a related instance of maximum flow problem: Si, add an ◦ Create a supersource O. For each supply node arc O → Si with capacity equal to the supply amount of Si . ◦ Create a supersink T. For each demand node Di, add an arc Di → T with capacity equal to the supply amount of Di . ◦ Find the maximum flow from O to T in the resulting auxiliary network. ◦ If maximum flow value = total demand then the current maximum flow is a feasible flow for17the 4 D1 11 5 B transshipment S1 problem, 17 else5 the transshipment2 problem is infeasible.

2

11 O 16

5 A 2 4

16

S2

19

T 15 C

9

8

5 D2

8

Solving the Transshipment Problem via Maximum Flow  In our example, ◦ The maximum flow from O to T is obtained by applying the Augmenting Path algorithm. The maximum flow value is 25. The bold red numbers on the arcs show the flow values. ◦ Since the maximum flow value = 25 = 17+8 = total demand, the current maximum flow4 is a feasible flow 17 4 D 11 S 5 5 1 B for the transshipment 1 5 2 9 17 17 problem. 2 2 11 5 T 13 1 O 16 2 A 2 8 2 15 8 5 16 4 19 9 8 18 S D2 8 C 2 16

Assignment Problem  Given:

n people and n jobs Each person can be assigned to exactly one job Each job should be assigned to exactly one person Person-job compatibility is given by a directed network (e.g., having a link A → x means “person A can do job x ”)  Goal: Find an assignment of n jobs to n people (if such an assignment exists). B C E A D people  Example: jobs

x

y

z

u

v

Solving the Assignment Problem via Maximum Flow 

The assignment problem can be solved by creating and solving a related instance of the transshipment problem: ◦ Each person-node is considered as a supply node with supply amount 1. ◦ Each job-node is considered as a demand node with demand amount 1. ◦ Assign capacity 1 to each arc. ◦ Solve the resulting transshipment problem by finding maximum flow in the auxiliary network. ◦ If maximum flow value = n then the current maximum flow gives a feasible assignment, 1 1 1 1 1 C E elseBthe assignment problem A D is infeasible. people

jobs

x

1

y

z 1

1

u

v 1

1

Solving the Assignment Problem via Maximum Flow  In our example, the red numbers on the arcs show the optimal flow values. Since the maximum flow value is 5, the assignment problem is feasible. O The feasible assignment is A → x , B → y, C → u , D → z 1 1 1 1 1 ,E→v. 1 1 1 1 1 B C E A D people 1

jobs

1

x

1

1

1

z

y 1

1

1

1

1

1

T

v

u 1

1 1

1

Showing the infeasibility of an assignment problem using maximum-flow-based arguments  Let’s solve the assignment problem below via maximum flow. The red numbers on the arcs show the optimal flow values. Since the maximum flow value = 5 < 6 = number of O jobs, the assignment problem is 1 1 1 1 1 infeasible. B C E F A D people 1

jobs

x

1

1

z

y 1 1

u

1

T

1 1

v

1

1

w

Showing the infeasibility of an assignment problem using minimum-cut-based arguments  The O-side of the minimum cut is {O, A, B, C, D, x, y, z} (the set of the nodes that are reachable from O via augmenting paths)  Return to the original network (delete nodes O and T and the arcs incident to them). O 1

1

jobs

B

A

people

x

1

1

1

C

1

D

1

E

1

z

y 1 1

u

1

T

1 1

v

F 1

1

w

Showing the infeasibility of an assignment problem using minimum-cut-based arguments  The capacity of the modified cut is 0 (since there are no arcs going from O-side to T-side).  There are 2 people (E, F) and 3 jobs (u, v, w) on T-side.  Thus, one of the 3 jobs should be assigned to a person from O-side (A, B, C, D).  But there are no arcs going from O-side to T-side. ( A, B, C, D can’t do the jobs u, v, w).  Thus, there is no way to assign the T-side jobs, and the assignment problem is B C E F A D people infeasible. jobs

x

y

z

u

v

w