You can use the min cost flow solver to solve special cases of the assignment problem.
In fact, min cost flow can often return a solution faster than either the MIP or CP-SAT solver. However, MIP and CP-SAT can solve a larger class of problems than min cost flow, so in most cases MIP or CP-SAT are the best choices.
The following sections present Python programs that solve the following assignment problems using the min cost flow solver:
- A minimal linear assignment example.
- An assignment problem with teams of workers.
Linear assignment example
This section show how to solve the example, described in the section Linear Assignment Solver, as a min cost flow problem.
Import the libraries
The following code imports the required library.
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
Declare the solver
The following code creates the minimum cost flow solver.
Python
# Instantiate a SimpleMinCostFlow solver. smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
Create the data
The flow diagram for the problem consists of the bipartite graph for the cost matrix (see the assignment overview for a slightly different example), with a source and sink added.
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.
Python
# 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]
)
source = 0
sink = 9
tasks = 4
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define four parallel arrays: sources, destinations, capacities,
// and unit costs between each pair. For instance, the arc from node 0
// to node 1 has a capacity of 15.
const std::vector<int64_t> 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> unit_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};
const int64_t source = 0;
const int64_t sink = 9;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
Java
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes =
new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
int[] endNodes =
new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
int[] capacities =
new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int[] unitCosts = new int[] {
0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0};
int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 };
int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 };
int[] 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 };
int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65,
125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 };
int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
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 (used by the linear assignment solver), flattened into a vector. - The third array corresponds to the arcs leading into the sink.
The data also includes the vector supplies, which gives the supply at each
node.
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 couldn't 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.
Python
# Add each arc.
for i in range(len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
# Add node supplies.
for i in range(len(supplies)):
smcf.set_node_supply(i, supplies[i])
C++
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
int arc = min_cost_flow.AddArcWithCapacityAndUnitCost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}
// Add node supplies.
for (int i = 0; i < supplies.size(); ++i) {
min_cost_flow.SetNodeSupply(i, supplies[i]);
}
Java
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = minCostFlow.addArcWithCapacityAndUnitCost(
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Add node supplies.
for (int i = 0; i < supplies.length; ++i) {
minCostFlow.setNodeSupply(i, supplies[i]);
}
C#
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc =
minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Add node supplies.
for (int i = 0; i < supplies.Length; ++i)
{
minCostFlow.SetNodeSupply(i, supplies[i]);
}
Invoke the solver
The following code invokes the solver and displays the solution.
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
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
Tail (start node) and the Head (end node) of the arc, which correspond to a
worker and task in the assignment.
Output of the program
Python
if status == smcf.OPTIMAL:
print("Total cost = ", smcf.optimal_cost())
print()
for arc in range(smcf.num_arcs()):
# Can ignore arcs leading out of source or into sink.
if smcf.tail(arc) != source and smcf.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 smcf.flow(arc) > 0:
print(
"Worker %d assigned to task %d. Cost = %d"
% (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
)
else:
print("There was an issue with the min cost flow input.")
print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
// Can ignore arcs leading out of source or into sink.
if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != 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(i) > 0) {
LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
<< " assigned to task " << min_cost_flow.Head(i)
<< " Cost: " << min_cost_flow.UnitCost(i);
}
}
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed.";
LOG(INFO) << "Solver status: " << status;
}
Java
if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Total cost: " + minCostFlow.getOptimalCost());
System.out.println();
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) {
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.getFlow(i) > 0) {
System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
+ minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
}
}
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
C#
if (status == MinCostFlow.Status.OPTIMAL)
{
Console.WriteLine("Total cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink)
{
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.Flow(i) > 0)
{
Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
" Cost: " + minCostFlow.UnitCost(i));
}
}
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed.");
Console.WriteLine("Solver status: " + status);
}
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.
The entire program
The entire program is shown below.
Python
"""Linear assignment example."""
from ortools.graph.python import min_cost_flow
def main():
"""Solving an Assignment Problem with MinCostFlow."""
# Instantiate a SimpleMinCostFlow solver.
smcf = min_cost_flow.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]
)
source = 0
sink = 9
tasks = 4
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
# Add each arc.
for i in range(len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
# Add node supplies.
for i in range(len(supplies)):
smcf.set_node_supply(i, supplies[i])
# Find the minimum cost flow between node 0 and node 10.
status = smcf.solve()
if status == smcf.OPTIMAL:
print("Total cost = ", smcf.optimal_cost())
print()
for arc in range(smcf.num_arcs()):
# Can ignore arcs leading out of source or into sink.
if smcf.tail(arc) != source and smcf.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 smcf.flow(arc) > 0:
print(
"Worker %d assigned to task %d. Cost = %d"
% (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
)
else:
print("There was an issue with the min cost flow input.")
print(f"Status: {status}")
if __name__ == "__main__":
main()
C++
#include <cstdint>
#include <vector>
#include "ortools/graph/min_cost_flow.h"
namespace operations_research {
// MinCostFlow simple interface example.
void AssignmentMinFlow() {
// Instantiate a SimpleMinCostFlow solver.
SimpleMinCostFlow min_cost_flow;
// Define four parallel arrays: sources, destinations, capacities,
// and unit costs between each pair. For instance, the arc from node 0
// to node 1 has a capacity of 15.
const std::vector<int64_t> 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> unit_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};
const int64_t source = 0;
const int64_t sink = 9;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
int arc = min_cost_flow.AddArcWithCapacityAndUnitCost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}
// Add node supplies.
for (int i = 0; i < supplies.size(); ++i) {
min_cost_flow.SetNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
int status = min_cost_flow.Solve();
if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
// Can ignore arcs leading out of source or into sink.
if (min_cost_flow.Tail(i) != source && min_cost_flow.Head(i) != 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(i) > 0) {
LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
<< " assigned to task " << min_cost_flow.Head(i)
<< " Cost: " << min_cost_flow.UnitCost(i);
}
}
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed.";
LOG(INFO) << "Solver status: " << status;
}
}
} // namespace operations_research
int main() {
operations_research::AssignmentMinFlow();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;
/** Minimal Assignment Min Flow. */
public class AssignmentMinFlow {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes =
new int[] {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8};
int[] endNodes =
new int[] {1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9};
int[] capacities =
new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int[] unitCosts = new int[] {
0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65, 125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0};
int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = minCostFlow.addArcWithCapacityAndUnitCost(
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Add node supplies.
for (int i = 0; i < supplies.length; ++i) {
minCostFlow.setNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
MinCostFlowBase.Status status = minCostFlow.solve();
if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Total cost: " + minCostFlow.getOptimalCost());
System.out.println();
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.getTail(i) != source && minCostFlow.getHead(i) != sink) {
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.getFlow(i) > 0) {
System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
+ minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
}
}
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
}
private AssignmentMinFlow() {}
}
C#
using System;
using Google.OrTools.Graph;
public class AssignmentMinFlow
{
static void Main()
{
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8 };
int[] endNodes = { 1, 2, 3, 4, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 5, 6, 7, 8, 9, 9, 9, 9 };
int[] 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 };
int[] unitCosts = { 0, 0, 0, 0, 90, 76, 75, 70, 35, 85, 55, 65,
125, 95, 90, 105, 45, 110, 95, 115, 0, 0, 0, 0 };
int source = 0;
int sink = 9;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc =
minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Add node supplies.
for (int i = 0; i < supplies.Length; ++i)
{
minCostFlow.SetNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
MinCostFlow.Status status = minCostFlow.Solve();
if (status == MinCostFlow.Status.OPTIMAL)
{
Console.WriteLine("Total cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.Tail(i) != source && minCostFlow.Head(i) != sink)
{
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.Flow(i) > 0)
{
Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
" Cost: " + minCostFlow.UnitCost(i));
}
}
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed.");
Console.WriteLine("Solver status: " + status);
}
}
}
Assignment with teams of workers
This section presents a more general assignment problem. 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.
For a MIP solver solution to this problem see Assignment with Teams of Workers.
The following sections describe a program that solves the problem using the min cost flow solver.
Import the libraries
The following code imports the required library.
Python
from ortools.graph.python import min_cost_flow
C++
#include <cstdint> #include <vector> #include "ortools/graph/min_cost_flow.h"
Java
import com.google.ortools.Loader; import com.google.ortools.graph.MinCostFlow; import com.google.ortools.graph.MinCostFlowBase;
C#
using System; using Google.OrTools.Graph;
Declare the solver
The following code creates the minimum cost flow solver.
Python
smcf = min_cost_flow.SimpleMinCostFlow()
C++
// Instantiate a SimpleMinCostFlow solver. SimpleMinCostFlow min_cost_flow;
Java
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
C#
// Instantiate a SimpleMinCostFlow solver. MinCostFlow minCostFlow = new MinCostFlow();
Create the data
The following code creates the data for the program.
Python
# Define the directed graph for the flow.
team_a = [1, 3, 5]
team_b = [2, 4, 6]
start_nodes = (
# fmt: off
[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]
# fmt: on
)
end_nodes = (
# fmt: off
[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]
# fmt: on
)
capacities = (
# fmt: off
[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]
# fmt: on
)
costs = (
# fmt: off
[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]
# fmt: on
)
source = 0
sink = 13
tasks = 4
# Define an array of supplies at each node.
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
C++
// Define the directed graph for the flow.
const std::vector<int64_t> team_A = {1, 3, 5};
const std::vector<int64_t> team_B = {2, 4, 6};
const std::vector<int64_t> 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};
const std::vector<int64_t> end_nodes = {
11, 12, 1, 3, 5, 2, 4, 6, 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> unit_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};
const int64_t source = 0;
const int64_t sink = 13;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, -tasks};
Java
// Define the directed graph for the flow.
// int[] teamA = new int[] {1, 3, 5};
// int[] teamB = new int[] {2, 4, 6};
int[] startNodes = new int[] {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};
int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 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};
int[] capacities = new int[] {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};
int[] unitCosts = new int[] {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};
int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
C#
// Define the directed graph for the flow.
int[] teamA = { 1, 3, 5 };
int[] teamB = { 2, 4, 6 };
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 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 };
int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 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 };
int[] 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 };
int[] unitCosts = { 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 };
int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
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.
Create the constraints
Python
# Add each arc.
for i in range(0, len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
# Add node supplies.
for i in range(0, len(supplies)):
smcf.set_node_supply(i, supplies[i])
C++
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
int arc = min_cost_flow.AddArcWithCapacityAndUnitCost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}
// Add node supplies.
for (int i = 0; i < supplies.size(); ++i) {
min_cost_flow.SetNodeSupply(i, supplies[i]);
}
Java
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = minCostFlow.addArcWithCapacityAndUnitCost(
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Add node supplies.
for (int i = 0; i < supplies.length; ++i) {
minCostFlow.setNodeSupply(i, supplies[i]);
}
C#
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc =
minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Add node supplies.
for (int i = 0; i < supplies.Length; ++i)
{
minCostFlow.SetNodeSupply(i, supplies[i]);
}
Invoke the solver
Python
# Find the minimum cost flow between node 0 and node 10. status = smcf.solve()
C++
// Find the min cost flow. int status = min_cost_flow.Solve();
Java
// Find the min cost flow. MinCostFlowBase.Status status = minCostFlow.solve();
C#
// Find the min cost flow. MinCostFlow.Status status = minCostFlow.Solve();
Output of the program
Python
if status == smcf.OPTIMAL:
print("Total cost = ", smcf.optimal_cost())
print()
for arc in range(smcf.num_arcs()):
# Can ignore arcs leading out of source or intermediate, or into sink.
if (
smcf.tail(arc) != source
and smcf.tail(arc) != 11
and smcf.tail(arc) != 12
and smcf.head(arc) != sink
):
# Arcs in the solution will have a flow value of 1.
# There start and end nodes give an assignment of worker to task.
if smcf.flow(arc) > 0:
print(
"Worker %d assigned to task %d. Cost = %d"
% (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
)
else:
print("There was an issue with the min cost flow input.")
print(f"Status: {status}")
C++
if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
// Can ignore arcs leading out of source or intermediate nodes, or into
// sink.
if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 &&
min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != 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(i) > 0) {
LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
<< " assigned to task " << min_cost_flow.Head(i)
<< " Cost: " << min_cost_flow.UnitCost(i);
}
}
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed.";
LOG(INFO) << "Solver status: " << status;
}
Java
if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Total cost: " + minCostFlow.getOptimalCost());
System.out.println();
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
// Can ignore arcs leading out of source or intermediate nodes, or into sink.
if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11
&& minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) {
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.getFlow(i) > 0) {
System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
+ minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
}
}
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
C#
if (status == MinCostFlow.Status.OPTIMAL)
{
Console.WriteLine("Total cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 &&
minCostFlow.Head(i) != sink)
{
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.Flow(i) > 0)
{
Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
" Cost: " + minCostFlow.UnitCost(i));
}
}
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed.");
Console.WriteLine("Solver status: " + status);
}
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.
Note that the min cost flow solver is faster for this problem than the MIP solver, which takes around 0.006 seconds.
The entire program
The entire program is shown below.
Python
"""Assignment with teams of workers."""
from ortools.graph.python import min_cost_flow
def main():
"""Solving an Assignment with teams of worker."""
smcf = min_cost_flow.SimpleMinCostFlow()
# Define the directed graph for the flow.
team_a = [1, 3, 5]
team_b = [2, 4, 6]
start_nodes = (
# fmt: off
[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]
# fmt: on
)
end_nodes = (
# fmt: off
[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]
# fmt: on
)
capacities = (
# fmt: off
[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]
# fmt: on
)
costs = (
# fmt: off
[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]
# fmt: on
)
source = 0
sink = 13
tasks = 4
# Define an array of supplies at each node.
supplies = [tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks]
# Add each arc.
for i in range(0, len(start_nodes)):
smcf.add_arc_with_capacity_and_unit_cost(
start_nodes[i], end_nodes[i], capacities[i], costs[i]
)
# Add node supplies.
for i in range(0, len(supplies)):
smcf.set_node_supply(i, supplies[i])
# Find the minimum cost flow between node 0 and node 10.
status = smcf.solve()
if status == smcf.OPTIMAL:
print("Total cost = ", smcf.optimal_cost())
print()
for arc in range(smcf.num_arcs()):
# Can ignore arcs leading out of source or intermediate, or into sink.
if (
smcf.tail(arc) != source
and smcf.tail(arc) != 11
and smcf.tail(arc) != 12
and smcf.head(arc) != sink
):
# Arcs in the solution will have a flow value of 1.
# There start and end nodes give an assignment of worker to task.
if smcf.flow(arc) > 0:
print(
"Worker %d assigned to task %d. Cost = %d"
% (smcf.tail(arc), smcf.head(arc), smcf.unit_cost(arc))
)
else:
print("There was an issue with the min cost flow input.")
print(f"Status: {status}")
if __name__ == "__main__":
main()
C++
#include <cstdint>
#include <vector>
#include "ortools/graph/min_cost_flow.h"
namespace operations_research {
// MinCostFlow simple interface example.
void BalanceMinFlow() {
// Instantiate a SimpleMinCostFlow solver.
SimpleMinCostFlow min_cost_flow;
// Define the directed graph for the flow.
const std::vector<int64_t> team_A = {1, 3, 5};
const std::vector<int64_t> team_B = {2, 4, 6};
const std::vector<int64_t> 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};
const std::vector<int64_t> end_nodes = {
11, 12, 1, 3, 5, 2, 4, 6, 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};
const std::vector<int64_t> 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};
const std::vector<int64_t> unit_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};
const int64_t source = 0;
const int64_t sink = 13;
const int64_t tasks = 4;
// Define an array of supplies at each node.
const std::vector<int64_t> supplies = {tasks, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, -tasks};
// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
int arc = min_cost_flow.AddArcWithCapacityAndUnitCost(
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}
// Add node supplies.
for (int i = 0; i < supplies.size(); ++i) {
min_cost_flow.SetNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
int status = min_cost_flow.Solve();
if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Total cost: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
// Can ignore arcs leading out of source or intermediate nodes, or into
// sink.
if (min_cost_flow.Tail(i) != source && min_cost_flow.Tail(i) != 11 &&
min_cost_flow.Tail(i) != 12 && min_cost_flow.Head(i) != 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(i) > 0) {
LOG(INFO) << "Worker " << min_cost_flow.Tail(i)
<< " assigned to task " << min_cost_flow.Head(i)
<< " Cost: " << min_cost_flow.UnitCost(i);
}
}
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed.";
LOG(INFO) << "Solver status: " << status;
}
}
} // namespace operations_research
int main() {
operations_research::BalanceMinFlow();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.graph.samples;
import com.google.ortools.Loader;
import com.google.ortools.graph.MinCostFlow;
import com.google.ortools.graph.MinCostFlowBase;
/** Minimal Assignment Min Flow. */
public class BalanceMinFlow {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();
// Define the directed graph for the flow.
// int[] teamA = new int[] {1, 3, 5};
// int[] teamB = new int[] {2, 4, 6};
int[] startNodes = new int[] {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};
int[] endNodes = new int[] {11, 12, 1, 3, 5, 2, 4, 6, 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};
int[] capacities = new int[] {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};
int[] unitCosts = new int[] {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};
int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = new int[] {tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks};
// Add each arc.
for (int i = 0; i < startNodes.length; ++i) {
int arc = minCostFlow.addArcWithCapacityAndUnitCost(
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}
// Add node supplies.
for (int i = 0; i < supplies.length; ++i) {
minCostFlow.setNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
MinCostFlowBase.Status status = minCostFlow.solve();
if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Total cost: " + minCostFlow.getOptimalCost());
System.out.println();
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
// Can ignore arcs leading out of source or intermediate nodes, or into sink.
if (minCostFlow.getTail(i) != source && minCostFlow.getTail(i) != 11
&& minCostFlow.getTail(i) != 12 && minCostFlow.getHead(i) != sink) {
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.getFlow(i) > 0) {
System.out.println("Worker " + minCostFlow.getTail(i) + " assigned to task "
+ minCostFlow.getHead(i) + " Cost: " + minCostFlow.getUnitCost(i));
}
}
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
}
private BalanceMinFlow() {}
}
C#
using System;
using Google.OrTools.Graph;
public class BalanceMinFlow
{
static void Main()
{
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();
// Define the directed graph for the flow.
int[] teamA = { 1, 3, 5 };
int[] teamB = { 2, 4, 6 };
// Define four parallel arrays: sources, destinations, capacities, and unit costs
// between each pair.
int[] startNodes = { 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 };
int[] endNodes = { 11, 12, 1, 3, 5, 2, 4, 6, 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 };
int[] 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 };
int[] unitCosts = { 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 };
int source = 0;
int sink = 13;
int tasks = 4;
// Define an array of supplies at each node.
int[] supplies = { tasks, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -tasks };
// Add each arc.
for (int i = 0; i < startNodes.Length; ++i)
{
int arc =
minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i)
throw new Exception("Internal error");
}
// Add node supplies.
for (int i = 0; i < supplies.Length; ++i)
{
minCostFlow.SetNodeSupply(i, supplies[i]);
}
// Find the min cost flow.
MinCostFlow.Status status = minCostFlow.Solve();
if (status == MinCostFlow.Status.OPTIMAL)
{
Console.WriteLine("Total cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
// Can ignore arcs leading out of source or into sink.
if (minCostFlow.Tail(i) != source && minCostFlow.Tail(i) != 11 && minCostFlow.Tail(i) != 12 &&
minCostFlow.Head(i) != sink)
{
// Arcs in the solution have a flow value of 1. Their start and end nodes
// give an assignment of worker to task.
if (minCostFlow.Flow(i) > 0)
{
Console.WriteLine("Worker " + minCostFlow.Tail(i) + " assigned to task " + minCostFlow.Head(i) +
" Cost: " + minCostFlow.UnitCost(i));
}
}
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed.");
Console.WriteLine("Solver status: " + status);
}
}
}