Solving an Assignment Problem with MinCostFlow
()
| 97 | |
| 98 | |
| 99 | def main(): |
| 100 | """Solving an Assignment Problem with MinCostFlow""" |
| 101 | |
| 102 | # Instantiate a SimpleMinCostFlow solver. |
| 103 | min_cost_flow = pywrapgraph.SimpleMinCostFlow() |
| 104 | # Define the directed graph for the flow. |
| 105 | |
| 106 | start_nodes = [0, 0, 0, 0] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4] + [5, 6, 7, 8] |
| 107 | end_nodes = [1, 2, 3, 4] + [5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8] + [9, 9, 9, 9] |
| 108 | capacities = [1, 1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1] |
| 109 | costs = ([0, 0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115] + [0, 0, 0, 0]) |
| 110 | # Define an array of supplies at each node. |
| 111 | supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4] |
| 112 | source = 0 |
| 113 | sink = 9 |
| 114 | tasks = 4 |
| 115 | |
| 116 | # Add each arc. |
| 117 | for i in range(len(start_nodes)): |
| 118 | min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], |
| 119 | capacities[i], costs[i]) |
| 120 | |
| 121 | # Add node supplies. |
| 122 | |
| 123 | for i in range(len(supplies)): |
| 124 | min_cost_flow.SetNodeSupply(i, supplies[i]) |
| 125 | # Find the minimum cost flow between node 0 and node 10. |
| 126 | if min_cost_flow.Solve() == min_cost_flow.OPTIMAL: |
| 127 | print('Total cost = ', min_cost_flow.OptimalCost()) |
| 128 | print() |
| 129 | for arc in range(min_cost_flow.NumArcs()): |
| 130 | |
| 131 | # Can ignore arcs leading out of source or into sink. |
| 132 | if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink: |
| 133 | |
| 134 | # Arcs in the solution have a flow value of 1. Their start and end nodes |
| 135 | # give an assignment of worker to task. |
| 136 | |
| 137 | if min_cost_flow.Flow(arc) > 0: |
| 138 | print('Worker %d assigned to task %d. Cost = %d' % ( |
| 139 | min_cost_flow.Tail(arc), |
| 140 | min_cost_flow.Head(arc), |
| 141 | min_cost_flow.UnitCost(arc))) |
| 142 | else: |
| 143 | print('There was an issue with the min cost flow input.') |
| 144 | |
| 145 | |
| 146 | if __name__ == '__main__': |