Assignment Problem Max Flow Meters

Here’s a problem: Your business assigns contractors to fulfill contracts. You look through your rosters and decide which contractors are available for a one month engagement and you look through your available contracts to see which of them are for one month long tasks. Given that you know how effectively each contractor can fulfill each contract, how do you assign contractors to maximize the overall effectiveness for that month?

This is an example of the assignment problem, and the problem can be solved with the classical Hungarian algorithm.

The Hungarian algorithm (also known as the Kuhn-Munkres algorithm) is a polynomial time algorithm that maximizes the weight matching in a weighted bipartite graph. Here, the contractors and the contracts can be modeled as a bipartite graph, with their effectiveness as the weights of the edges between the contractor and the contract nodes.

In this article, you will learn about an implementation of the Hungarian algorithm that uses the Edmonds-Karp algorithm to solve the linear assignment problem. You will also learn how the Edmonds-Karp algorithm is a slight modification of the Ford-Fulkerson method and how this modification is important.

The Maximum Flow Problem

The maximum flow problem itself can be described informally as the problem of moving some fluid or gas through a network of pipes from a single source to a single terminal. This is done with an assumption that the pressure in the network is sufficient to ensure that the fluid or gas cannot linger in any length of pipe or pipe fitting (those places where different lengths of pipe meet).

By making certain changes to the graph, the assignment problem can be turned into a maximum flow problem.

Preliminaries

The ideas needed to solve these problems arise in many mathematical and engineering disciplines, often similar concepts are known by different names and expressed in different ways (e.g., adjacency matrices and adjacency lists). Since these ideas are quite esoteric, choices are made regarding how generally these concepts will be defined for any given setting.

This article will not assume any prior knowledge beyond a little introductory set theory.

The implementations in this post represent the problems as directed graphs (digraph).

DiGraphs

digraph has two attributes, setOfNodes and setOfArcs. Both of these attributes are sets (unordered collections). In the code blocks on this post, I’m actually using Python’s frozenset, but that detail isn’t particularly important.

(Note: This, and all other code in this article, are written in Python 3.6.)

Nodes

node is composed of two attributes:

  • : This represents any data object.

Arcs

An arc is composed of three attributes:

  • : This is a node, as defined above.
  • : This is a node, as defined above.
  • : This represents any data object.

The set of arcs in the digraph represents a binary relation on the nodes in the digraph. The existence of arc implies that a relationship exists between  and .

In a directed graph (as opposed to an undirected graph), the existence of a relationship between and  does not imply that a similar relationship between  and  exists.

This is because in an undirected graph, the relationship being expressed is not necessarily symmetric.

DiGraphs

Nodes and arcs can be used to define a digraph, but for convenience, in the algorithms below, a digraph will be represented using as a dictionary.

Here’s a method that can convert the graph representation above into a dictionary representation similar to this one:

And here’s another one that converts it into a dictionary of dictionaries, another operation that will be useful:

When the article talks about a digraph as represented by a dictionary, it will mention  to refer to it.

Sometimes it’s helpful to fetch a node from a digraph by it up through its  (unique identifier):

In defining graphs, people sometimes use the terms node and vertex to refer to the same concept; the same is true of the terms arc and edge.

Two popular graph representations in Python are this one which uses dictionaries and another which uses objects to represent graphs. The representation in this post is somewhere in between these two commonly used representations.

This is my digraph representation. There are many like it, but this one is mine.

Walks and Paths

Let  be a finite sequence (ordered collection) of arcs in a digraph such that if  is any arc in  except for the last, and  follows  in the sequence, then there must be a node in  such that .

Starting from the first arc in , and continuing until the last arc in , collect (in the order encountered) all nodes as defined above between each two consecutive arcs in . Label the ordered collection of nodes collected during this operation .

  • If any node appears more than once in the sequence  then call  a Walk on digraph.
  • Otherwise, call  a path from  to  on digraph.

Source Node

Call node a source node in digraph if  is in  and  contains no arc such that .

Terminal Node

Call node a terminal node in digraph if  is in  and  contains no arc such that .

Cuts and s-t Cuts

A cut of a connecteddigraph is a subset of arcs from  which partitions the set of nodes in .  is connected if every node in  and has at least one arc in  such that either  or , but .

The definition above refers to a subset of arcs, but it can also define a partition of the nodes of .

For the functions  and ,  is a node in set G.setOfNodes of digraph, and  is a cut of :

Let  be a cut of digraph.

 is a cut of digraph if:  is called an x-y cut if . When the node in a x-y cut is a source node and node in the x-y cut is a terminal node, then this cut is called a s-t cut.

Flow Networks

You can use a digraph to represent a flow network.

Assign each node, where  is in  an  that is a :

Assign each arc, where  is in  and  that is a .

 and  are positivereal numbers.

 and  are also positive real numbers.

For every node node in :

Digraph now represents a flow network.

The flow of  refers to the  for all arcs in .

Feasible Flows

Let digraph represent a flow network.

The flow network represented by  has feasible flows if:

  1. For every node in  except for source nodes and terminal nodes : .
  2. For every arc in : .

Condition 1 is called a conservation constraint.

Condition 2 is called a capacity constraint.

Cut Capacity

The cut capacity of an s-t cut with source node and terminal node of a flow networkrepresented by a digraph is:

Minimum Capacity Cut

Let  be an s-t cut of a flow network represented by a digraph.

 is the minimum capacity cut of the flow network represented by  if there is no other s-t cut in this flow network such that:

Stripping the Flows Away

I would like to refer to the digraph that would be the result of taking a digraph and stripping away all the flow data from all the nodes in  and also all the arcs in .

Maximum Flow Problem

flow network represented as a digraph, a source node in  and a terminal node in ,  can represent a maximum flow problem if:

Label this representation:

Where , , and  is an identifier for the problem instance.

Maximum Flow Solution

Let  represent a maximum flow problem. The solution to  can be represented by a flow network represented as a digraph.

Digraph is a feasible solution to the maximum flow problem on input  if:

  1. .
  2.  is a flow network and has feasible flows.

If in addition to 1 and 2:

  1. There can be no other flow network represented by digraph such that  and .

Then  is also an optimal solution to .

In other words a feasible maximum flow solution can be represented by a digraph, which:

  1. Is identical to digraph of the corresponding maximum flow problem with the exception that the ,  and the  of any of the nodes and arcs may be different.
  2. Represents a flow network that has feasible flows.

And, it can represent an optimal maximum flow solution if additionally:

  1. The  for the node corresponding to the terminal node in the maximum flow problem is as large as possible (when conditions 1 and 2 are still satisfied).

If digraph represents a feasible maximum flow solution :  this follows from the max flow, min cut theorem (discussed below). Informally, since  is assumed to have feasible flows this means that flow can neither be ‘created’ (except at source node) nor ‘destroyed’ (except at terminal node) while crossing any (other) node (conservation constraints).

Since a maximum flow problem contains only a single source node and a single terminal node, all flow ‘created’ at  must be ‘destroyed’ at  or the flow network does not have feasible flows (the conservation constraint would have been violated).

Let digraph represent a feasible maximum flow solution; the value above is called the s-t Flow Value of .

Let:

This means that  is a successor state of , which just means that  is exacly like  with the exception that the values of  for arcs  in  may be different than  for arcs  in .

Here’s a visualization of a  along with its associated . Each arc in the image has a label, these labels are , each node in the image has a label, and these labels are .

s-t Cut Flow

Let  represent a  and let  represent a cut of . The cut flow of  is defined:

s-t cut flow is the sum of flows from the partition containing the source node to the partition containing the terminal node minus the sum of flows from the partition containing the terminal node to the partition containing the source node.

Max Flow, Min Cut

Let  represent a maximum flow problem and let the solution to  be represented by a flow network represented as digraph.

Let  be the minimum capacity cut of the flow network represented by .

Because in the maximum flow problem flow originates in only a single source node and terminates at a single terminal node and, because of the capacity constraints and the conservation constraints, we know that the all of the flow entering  must cross any s-t cut, in particular it must cross . This means:

Solving the Maximum Flow Problem

The basic idea for solving a maximum flow problem is to start with a maximum flow solutionrepresented by digraph. Such a starting point can be . The task is then to use  and by some greedy modification of the  values of some arcs in  to produce another maximum flow solution represented by digraph such that  cannot still represent a flow network with feasible flows and . As long as this process continues, the quality () of the most recently encountered maximum flow solution () is better than any other maximum flow solution that has been found. If the process reaches a point that it knows that no other improvement is possible, the process can terminate and it will return the optimalmaximum flow solution.

The description above is general and skips many proofs such as whether such a process is possible or how long it may take, I’ll give a few more details and the algorithm.

The Max Flow, Min Cut Theorem

From the book Flows in Networks by Ford and Fulkerson, the statement of the max flow, min cut theorem(Theorem 5.1) is:

For any network, the maximal flow value from  to  is equal to the minimum cut capacity of all cuts separating  and .

Using the definitions in this post, that translates to:

The solution to a  represented by a flow network represented as digraph is optimal if:

I like this proof of the theorem and Wikipedia has another one.

The max flow, min cut theorem is used to prove the correctness and completeness of the Ford-Fulkerson method.

I’ll also give a proof of the theorem in the section after augmenting paths.

The Ford-Fulkerson Method and the Edmonds-Karp Algorithm

CLRS defines the Ford-Fulkerson method like so (section 26.2):

Residual Graph

The Residual Graph of a flow network represented as the digraph can be represented as a digraph:

  •  returns the sum of  for all arcs in the subset of  where arc is in the subset if  and .
  •  returns the sum of  for all arcs in the subset of where arc is in the subset if  and .

Briefly, the residual graph represents certain actions which can be performed on the digraph.

Each pair of nodes in  of the flow network represented by digraph can generate 0, 1, or 2 arcs in the residual graph of .

  1. The pair  does not generate any arcs in  if there is no arc in  such that  and .
  2. The pair  generates the arc in  where  represents an arc labeled a push flow arcfrom  to  if .
  3. The pair  generates the arc in  where  represents an arc labeled a pull flow arcfrom  to  if .
  • Each push flow arc in  represents the action of adding a total of  flow to arcs in the subset of  where arc is in the subset if  and .
  • Each pull flow arc in  represents the action of subtracting a total of flow to arcs in the subset of  where arc is in the subset if  and .

Performing an individual push or pull action from  on the applicable arcs in  might generate a flow network without feasible flows because the capacity constraints or the conservation constraints might be violated in the generated flow network.

Here’s a visualization of the residual graph of the previous example visualization of a maximum flow solution, in the visualization each arc represents .

Augmenting Path

Let  be a max flow problem, and let  be the residual graph of .

An augmenting path for  is any path from  to .

It turns out that an augmenting path can be applied to a max flow solution represented by digraph generating another max flow solution represented by digraph where  if  is not optimal.

Here’s how:

In the above,  is some tolerance value for rounding the flow values in the network. This is to avoid cascading imprecision of floating point calculations. So, for example, I used  to mean round to 10 significant digits.

Let , then  represents a feasible max flow solution for . For the statement to be true, the flow network represented by  must have feasible flows (not violate the capacity constraint or the conservation constraint.

Here’s why: In the method above, each node added to the new flow network represented by digraph is either an exact copy of a node from digraph or a node which has had the same number added to its  as its . This means that the conservation constraint is satisfied in  as long as it was satisfied in . The conservation constraint is satisfied because we explicitly check that any new arc in the network has ; thus, as long as the arcs from the set which were copied unmodified into  do not violate the capacity constraint, then  does not violate the capacity constraint.

It’s also true that  if  is not optimal.

Here’s why: For an augmenting path to exist in the digraph representation of the residual graph of a max flow problem then the last arc on  must be a ‘push’ arc and it must have . An augmenting path is defined as one which terminates at the terminal node of the max flow problem for which it is an augmenting path. From the definition of the residual graph, it is clear that the last arc in an augmenting path on that residual graph must be a ‘push’ arc because any ‘pull’ arc in the augmenting path will have  and  from the definition of path. Additionally, from the definition of path, it is clear that the terminal node is only modified once by the  method. Thus  modifies  exactly once and it increases the value of  because the last arc in the  must be the arcwhich causes the modification in  during . From the definition of  as it applies to ‘push’ arcs, the  can only be increased, not decreased.

Some Proofs from Sedgewick and Wayne

The book Algorithms, fourth edition by Robert Sedgewich and Kevin Wayne has some wonderful and short proofs (pages 892-894) that will be useful. I’ll recreate them here, though I’ll use language fitting in with previous definitions. My labels for the proofs are the same as in the Sedgewick book.

Proposition E: For any digraph representing a feasible maximum flow solution to a maximum flow problem, for any .

Proof: Let . Proposition E holds for  directly from the definition of s-t flow value. Suppose that there we wish to move some node from the s-partition () and into the t-partition , to do so we need to change , which could change  and invalidate proposition E. However, let’s see how the value of  will change as we make this change. node is at equilibrium meaning that the sum of flow into node is equal to the sum of flow out of it (this is necessary for  to represent a feasible solution). Notice that all flow which is part of the  entering node enters it from the s-partition (flow entering node from the t-partition either directly or indirectly would not have been counted in the  value because it is heading the wrong direction based on the definition). Additionally, all flow exiting  will eventually (directly or indirectly) flow into the terminal node (proved earlier). When we move node into the t-partition, all the flow entering  from the s-partition must be added to the new value; however, all flow exiting  must the be subtracted from the new  value; the part of the flow heading directly into the t-partition is subtracted because this flow is now internal to the new t-partition and is not counted as . The part of the flow from  heading into nodes in the s-partition must also be subtracted from : After  is moved into the t-partition, these flows will be directed from the t-partition and into the s-partition and so must not be accounted for in the , since these flows are removed the inflow into the s-partition and must be reduced by the sum of these flows, and the outflow from the s-partition into the t-partition (where all flows from s-t must end up) must be reduced by the same amount. As node was at equilibrium prior to the process, the update will have added the same value to the new  value as it subtracted thus leaving proposition E true after the update. The validity of proposition E then follows from induction on the size of the t-partition.

Here are some example flow networks to help visualize the less obvious cases where proposition E holds; in the image, the red areas indicate the s-partition, the blue areas represent the t-partition, and the green arcsindicate an s-t cut. In the second image, flow between node A and node B increases while the flow into terminal node t doesn’t change.:

Corollary: No s-t cut flow value can exceed the capacity of any s-t cut.

Proposition F. (max flow, min cut theorem): Let  be an s-t flow. The following 3 conditions are equivalent:

  1. There exists an s-t cut whose capacity equals the value of the flow .
  2.  is a max flow.
  3. There is no augmenting path with respect to .

Condition 1 implies condition 2 by the corollary. Condition 2 implies condition 3 because the existence of an augmenting path implies the existence of a flow with larger values, contradicting the maximality of . Condition 3 implies condition 1: Let  be the set of all nodes that can be reached from  with an augmenting path in the residual graph. Let  be the remaining arcs, then  must be in  (by our assumption). The arcs crossing from  to  then form an s-t cut which contains only arcs where either  or . If this were otherwise then the nodesconnected by an arc with remaining residual capacity to  would be in the set  since there would then be an augmenting path from  to such a node. The flow across the s-t cut is equal to the s-t cut’s capacity (since arcs from  to  have flow equal to capacity) and also to the value of the s-t flow (by proposition E).

This statement of the max flow, min cut theorem implies the earlier statement from Flows in Networks.

Corollary (integrality property): When capacities are integers, there exists an integer-valued max flow, and the Ford-Fulkerson algorithm finds it.

Proof: Each augmenting path increases the flow by a positive integer, the minimum of the unused capacities in the ‘push’ arcs and the flows in the ‘pull’ arcs, all of which are always positive integers.

This justifies the Ford-Fulkerson method description from CLRS. The method is to keep finding augmenting paths and applying  to the latest  coming up with better solutions, until no more augmenting path meaning that the latest maximum flow solution is optimal.

From Ford-Fulkerson to Edmonds-Karp

The remaining questions regarding solving maximum flow problems are:

  1. How should augmenting paths be constructed?
  2. Will the method terminate if we use real numbers and not integers?
  3. How long will it take to terminate (if it does)?

The Edmonds-Karp algorithm specifies that each augmenting path is constructed by a breadth first search(BFS) of the residual graph; it turns out that this decision of point 1 above will also force the algorithm to terminate (point 2) and allows the asymptotic time and space complexity to be determined.

First, here’s a BFS implementation:

I used a deque from the python collections module.

To answer question 2 above, I’ll paraphrase another proof from Sedgewick and Wayne: Proposition G. The number of augmenting paths needed in the Edmonds-Karp algorithm with nodes and arcs is at most . Proof: Every augmenting path has a bottleneckarc– an arc that is deleted from the residual graphbecause it corresponds either to a ‘push’ arc that becomes filled to capacity or a ‘pull’ arc through which the flow becomes 0. Each time an arc becomes a bottleneck arc, the length of any augmenting path through it must increase by a factor of 2. This is because each node in a path may appear only once or not at all (from the definition of path) since the paths are being explored from shortest path to longest that means that at least one more node must be visited by the next path that goes through the particular bottleneck node that means an additional 2 arcs on the path before we arrive at the node. Since the augmenting path is of length at most  each arc can be on at most augmenting paths, and the total number of augmenting paths is at most .

The Edmonds-Karp algorithm executes in . If at most paths will be explored during the algorithm and exploring each path with BFS is  then the most significant term of the product and hence the asymptotic complexity is .

Let  be a .

The version above is inefficient and has worse complexity than  since it constructs a new maximum flow solution and new a residual graph each time (rather than modifying existing digraphs as the algorithm advances). To get to a true  solution the algorithm must maintain both the digraph representing the maximum flow problem state and its associated residual graph. So the algorithm must avoid iterating over arcs and nodes unnecessarily and update their values and associated values in the residual graph only as necessary.

To write a faster Edmonds Karp algorithm, I rewrote several pieces of code from the above. I hope that going through the code which generated a new digraph was helpful in understanding what’s going on. In the fast algorithm, I use some new tricks and Python data structures that I don’t want to go over in detail. I will say that  and  are now treated as strings and uids to nodes. For this code, let  be a 

Here’s a visualization of how this algorithm solves the example flow network from above. The visualization shows the steps as they are reflected in the digraph representing the most up-to-date flow network and as they are reflected in the residual graph of that flow network. Augmenting paths in the residual graph are shown as red paths, and the digraph representing the problem the set of nodes and arcs affected by a given augmenting path is highlighted in green. In each case, I’ll highlight the parts of the graph that will be changed (in red or green) and then show the graph after the changes (just in black).

Here’s another visualization of how this algorithm solving a different example flow network. Notice that this one uses real numbers and contains multiple arcs with the same  and  values.

**Also notice that because Arcs with a ‘pull’ ResidualDatum may be part of the Augmenting Path, the nodes affected in the DiGraph of the Flown Network _may not be on a path in .

Bipartite Graphs

Suppose we have a digraph,  is bipartite if it’s possible to partition the nodes in  into two sets ( and ) such that for any arc in  it cannot be true that  in  and  in . It also cannot be true that  in  and  in .

In other words  is bipartite if it can be partitioned into two sets of nodes such that every arc must connect a node in one set to a node in the other set.

Testing Bipartite

Suppose we have a digraph, we want to test if it is bipartite. We can do this in  by greedy coloring the graph into two colors.

First, we need to generate a new digraph. This graph will have will have the same set of nodes as , but it will have more 

Please follow and like us:

Overview

The previous section showed how to solve an assignment problem with the linear assignment solver. This section shows how to solve the same problem with the more general minimum cost flow solver. While linear assignment is faster than min cost flow for this particular problem, min cost flow can solve a larger class of problems. Typically, a solver designed for a special class of problems will solve those problems faster than a solver that can handle a more general class of problems.

The following sections present a Python program that solves the assignment problem using min cost flow.

Create the solver

The following code creates the minimum cost flow solver.

from ortools.graph import pywrapgraph import time def main(): """Solving an Assignment Problem with MinCostFlow""" # Instantiate a SimpleMinCostFlow solver. min_cost_flow = pywrapgraph.SimpleMinCostFlow()

Create the data

The flow diagram for the problem is the bipartite graph from the problem with the previous section, with a source and sink added.

Note: The numbering of the workers and tasks is different from that of original example, because the min cost flow solver requires all nodes in the graph to be numbered distinctly

The data contains the following four arrays, corresponding to the start nodes, end nodes, capacities, and costs for the problem. The length of each array is the number of arcs in the graph.

# Define the directed graph for the flow. 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] 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] 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 ] 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])

To make clear how the data is set up, each array is divided into three sub-arrays:

  • The first array corresponds to arcs leading out of the source.
  • The second array corresponds to the arcs between workers and tasks. For the costs, this is just the cost matrix, flattened into a vector.
  • The third array corresponds to the arcs leading into the sink.

The data also includes the following vector , which gives the supply at each node.

supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4]

How a min cost flow problem represents an assignment problem

How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1.

Next, the flow-in-equals-flow-out condition forces the flow out of each worker to be 1. If possible, the solver would direct that flow across the minimum cost arc leading out of each worker. However, the solver cannot direct the flows from two different workers to a single task. If it did, there would be a combined flow of 2 at that task, which could not be sent across the single arc with capacity 1 from the task to the sink. This means that the solver can only assign a task to a single worker, as required by the assignment problem.

Finally, the flow-in-equals-flow-out condition forces each task to have an outflow of 1, so each task is performed by some worker.

Create the graph and constraints

The following code creates the graph and constraints.

# Add each arc. for i in range(len(start_nodes)): min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], capacities[i], costs[i]) # Add node supplies. for i in range(len(supplies)): min_cost_flow.SetNodeSupply(i, supplies[i])

Invoke the solver

The following code invokes the solver and displays the solution.

if min_cost_flow.Solve() == min_cost_flow.OPTIMAL: print('Total cost = ', min_cost_flow.OptimalCost()) print() for arc in range(min_cost_flow.NumArcs()): # Can ignore arcs leading out of source or into sink. if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if min_cost_flow.Flow(arc) > 0: print('Worker %d assigned to task %d. Cost = %d' % ( min_cost_flow.Tail(arc), min_cost_flow.Head(arc), min_cost_flow.UnitCost(arc))) else: print('There was an issue with the min cost flow input.') The solution consists of the arcs between workers and tasks that are assigned a flow of 1 by the solver. (Arcs connected to the source or sink are not part of the solution.) The program checks each arc to see if it has flow 1, and if so, prints the (start node) and the (end node) of the arc, which correspond to a worker and task in the assignment.

Output of the program

Here is the output of the program.

Total cost = 265 Worker 1 assigned to task 8. Cost = 70 Worker 2 assigned to task 7. Cost = 55 Worker 3 assigned to task 6. Cost = 95 Worker 4 assigned to task 5. Cost = 45 Time = 0.000245 seconds The result is the same as that for the linear assignment solver (except for the different numbering of workers and costs). The linear assignment solver is slightly faster than min cost flow — 0.000147 seconds versus 0.000458 seconds — which might be a consideration for a much larger assignment problem.

The entire program

The entire program is shown below.

from __future__ import print_function from ortools.graph import pywrapgraph import time def main(): """Solving an Assignment Problem with MinCostFlow""" # Instantiate a SimpleMinCostFlow solver. min_cost_flow = pywrapgraph.SimpleMinCostFlow() # Define the directed graph for the flow. 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] 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] 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 ] 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]) # Define an array of supplies at each node. supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, -4] source = 0 sink = 9 tasks = 4 # Add each arc. for i in range(len(start_nodes)): min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], capacities[i], costs[i]) # Add node supplies. for i in range(len(supplies)): min_cost_flow.SetNodeSupply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. if min_cost_flow.Solve() == min_cost_flow.OPTIMAL: print('Total cost = ', min_cost_flow.OptimalCost()) print() for arc in range(min_cost_flow.NumArcs()): # Can ignore arcs leading out of source or into sink. if min_cost_flow.Tail(arc)!=source and min_cost_flow.Head(arc)!=sink: # Arcs in the solution have a flow value of 1. Their start and end nodes # give an assignment of worker to task. if min_cost_flow.Flow(arc) > 0: print('Worker %d assigned to task %d. Cost = %d' % ( min_cost_flow.Tail(arc), min_cost_flow.Head(arc), min_cost_flow.UnitCost(arc))) else: print('There was an issue with the min cost flow input.') if __name__ == '__main__': start_time = time.clock() main() print() print("Time =", time.clock() - start_time, "seconds")

Balance the workload between two groups of workers

This section presents a more general assignment problem, which can't be solved by the linear assignment solver. In this problem, six workers are divided into two teams. The problem is to assign four tasks to the workers so that the workload is equally balanced between the teams — that is, so each team performs two of the tasks.

Create the data and constraints

The following code creates the data and constraints for the program.

# Define the directed graph for the flow. team_A = [1, 3, 5] team_B = [2, 4, 6] start_nodes = ([0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10]) end_nodes = ([11, 12] + team_A + team_B + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13]) capacities = ([2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]) costs = ([0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0]) # Define an array of supplies at each node. supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4] source = 0 sink = 13

The workers correspond to nodes 1 - 6. Team A consists of workers 1, 3, and 5, and team B consists of workers 2, 4, and 6. The tasks are numbered 7 - 10.

There are two new nodes, 11 and 12, between the source and workers. Node 11 is connected to the nodes for team A, and Node 12 is connected to the nodes for team B, with arcs of capacity 1. The graph below shows just the nodes and arcs from the source to the workers.

The key to balancing the workload is that the source 0 is connected to nodes 11 and 12 by arcs of capacity 2. This means that nodes 11 and 12 (and therefore teams A and B) can have a maximum flow of 2. As a result, each team can perform at most two of the tasks.

Output of the program

The following shows the output of the program.

Total cost = 250 Worker 1 assigned to task 9. Cost = 75 Worker 2 assigned to task 7. Cost = 35 Worker 5 assigned to task 10. Cost = 75 Worker 6 assigned to task 8. Cost = 65 Time = 0.00031 seconds

Team A is assigned tasks 9 and 10, while team B is assigned tasks 7 and 8.

The entire program

The entire program is shown below.

from __future__ import print_function from ortools.graph import pywrapgraph import time def main(): """Solving Assignment Problem with MinCostFlow""" # Instantiate a SimpleMinCostFlow solver. min_cost_flow = pywrapgraph.SimpleMinCostFlow() # Define the directed graph for the flow. team_A = [1, 3, 5] team_B = [2, 4, 6] start_nodes = ([0, 0] + [11, 11, 11] + [12, 12, 12] + [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6] + [7, 8, 9, 10]) end_nodes = ([11, 12] + team_A + team_B + [7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10, 7, 8, 9, 10] + [13, 13, 13, 13]) capacities = ([2, 2] + [1, 1, 1] + [1, 1, 1] + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] + [1, 1, 1, 1]) costs = ([0, 0] + [0, 0, 0] + [0, 0, 0] + [90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 60, 105, 80, 75, 45, 65, 110, 95] + [0, 0, 0, 0]) # Define an array of supplies at each node. supplies = [4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4] source = 0 sink = 13 # Add each arc. for i in range(0, len(start_nodes)): min_cost_flow.AddArcWithCapacityAndUnitCost(start_nodes[i], end_nodes[i], capacities[i], costs[i]) # Add node supplies. for i in range(0, len(supplies)): min_cost_flow.SetNodeSupply(i, supplies[i]) # Find the minimum cost flow between node 0 and node 10. if min_cost_flow.Solve() == min_cost_flow.OPTIMAL: min_cost_flow.Solve() print('Total cost = ', min_cost_flow.OptimalCost()) print() for arc in range(min_cost_flow.NumArcs()): # Can ignore arcs leading out of source or intermediate nodes, or into sink. if (min_cost_flow.Tail(arc)!=0 and min_cost_flow.Tail(arc)!=11 and min_cost_flow.Tail(arc)!=12 and min_cost_flow.Head(arc)!=13): # Arcs in the solution will have a flow value of 1. There start and end nodes # give an assignment of worker to task. if min_cost_flow.Flow(arc) > 0: print('Worker %d assigned to task %d. Cost = %d' % ( min_cost_flow.Tail(arc), min_cost_flow.Head(arc), min_cost_flow.UnitCost(arc))) else: print('There was an issue with the min cost flow input.') if __name__ == '__main__': start_time = time.clock() main() print() print("Time =", time.clock() - start_time, "seconds")
Categories: 1

0 Replies to “Assignment Problem Max Flow Meters”

Leave a comment

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *