Solving an Assignment Problem with MinCostFlow" :param adj_mat: adjacency matrix with binary values indicating possible matchings between two sets :param cost_mat: cost matrix recording the matching cost of every possible pair of items from two sets :return:
(adj_mat, cost_mat)
| 30 | |
| 31 | |
| 32 | def SolveMinCostFlow(adj_mat, cost_mat): |
| 33 | """ |
| 34 | Solving an Assignment Problem with MinCostFlow" |
| 35 | :param adj_mat: adjacency matrix with binary values indicating possible matchings between two sets |
| 36 | :param cost_mat: cost matrix recording the matching cost of every possible pair of items from two sets |
| 37 | :return: |
| 38 | """ |
| 39 | |
| 40 | # Instantiate a SimpleMinCostFlow solver. |
| 41 | min_cost_flow = pywrapgraph.SimpleMinCostFlow() |
| 42 | # Define the directed graph for the flow. |
| 43 | |
| 44 | cnt_1, cnt_2 = adj_mat.shape |
| 45 | cnt_nonzero_row = int(np.sum(np.sum(adj_mat, axis=1) > 0)) |
| 46 | cnt_nonzero_col = int(np.sum(np.sum(adj_mat, axis=0) > 0)) |
| 47 | |
| 48 | # prepare directed graph for the flow |
| 49 | start_nodes = np.zeros(cnt_1, dtype=np.int).tolist() +\ |
| 50 | np.repeat(np.array(range(1, cnt_1+1)), cnt_2).tolist() + \ |
| 51 | [i for i in range(cnt_1+1, cnt_1 + cnt_2 + 1)] |
| 52 | end_nodes = [i for i in range(1, cnt_1+1)] + \ |
| 53 | np.repeat(np.array([i for i in range(cnt_1+1, cnt_1 + cnt_2 + 1)]).reshape([1, -1]), cnt_1, axis=0).flatten().tolist() + \ |
| 54 | [cnt_1 + cnt_2 + 1 for i in range(cnt_2)] |
| 55 | capacities = np.ones(cnt_1, dtype=np.int).tolist() + adj_mat.flatten().astype(np.int).tolist() + np.ones(cnt_2, dtype=np.int).tolist() |
| 56 | costs = (np.zeros(cnt_1, dtype=np.int).tolist() + cost_mat.flatten().astype(np.int).tolist() + np.zeros(cnt_2, dtype=np.int).tolist()) |
| 57 | # Define an array of supplies at each node. |
| 58 | supplies = [min(cnt_nonzero_row, cnt_nonzero_col)] + np.zeros(cnt_1 + cnt_2, dtype=np.int).tolist() + [-min(cnt_nonzero_row, cnt_nonzero_col)] |
| 59 | # supplies = [min(cnt_1, cnt_2)] + np.zeros(cnt_1 + cnt_2, dtype=np.int).tolist() + [-min(cnt_1, cnt_2)] |
| 60 | source = 0 |
| 61 | sink = cnt_1 + cnt_2 + 1 |
| 62 | |
| 63 | # Add each arc. |
| 64 | for i in range(len(start_nodes)): |
| 65 | min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], |
| 66 | capacities[i], costs[i]) |
| 67 | |
| 68 | # Add node supplies. |
| 69 | for i in range(len(supplies)): |
| 70 | min_cost_flow.SetNodeSupply(i, supplies[i]) |
| 71 | |
| 72 | match_results = [] |
| 73 | # Find the minimum cost flow between node 0 and node 10. |
| 74 | if min_cost_flow.Solve() == min_cost_flow.OPTIMAL: |
| 75 | # print('Total cost = ', min_cost_flow.OptimalCost()) |
| 76 | # print() |
| 77 | for arc in range(min_cost_flow.NumArcs()): |
| 78 | |
| 79 | # Can ignore arcs leading out of source or into sink. |
| 80 | if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink: |
| 81 | |
| 82 | # Arcs in the solution have a flow value of 1. Their start and end nodes |
| 83 | # give an assignment of worker to task. |
| 84 | |
| 85 | if min_cost_flow.Flow(arc) > 0: |
| 86 | # print('set A item %d assigned to set B item %d. Cost = %d' % ( |
| 87 | # min_cost_flow.Tail(arc)-1, |
| 88 | # min_cost_flow.Head(arc)-cnt_1-1, |
| 89 | # min_cost_flow.UnitCost(arc))) |