# Minimum Cost Flows

Closely related to the max flow problem is the minimum cost (min cost) flow problem, in which each arc in the graph has a unit cost for transporting material across it. The problem is to find a flow with the least total cost.

The min cost flow problem also has special nodes, called supply nodes or demand nodes, which are similar to the source and sink in the max flow problem. Material is transported from supply nodes to demand nodes.

• At a supply node, a positive amount — the supply — is added to the flow. A supply could represent production at that node, for example.
• At a demand node, a negative amount — the demand — is taken away from the flow. A demand could represent consumption at that node, for example.

For convenience, we'll assume that all nodes, other than supply or demand nodes, have zero supply (and demand).

For the min cost flow problem, we have the following flow conservation rule, which takes the supplies and demands into account:

The graph below shows a min cost flow problem. The arcs are labeled with pairs of numbers: the first number is the capacity and the second number is the cost. The numbers in parentheses next to the nodes represent supplies or demands. Node 0 is a supply node with supply 20, while nodes 3 and 4 are demand nodes, with demands -5 and -15, respectively. ### Import the libraries

The following code imports the required library.

### Python

`from ortools.graph import pywrapgraph`

### C++

```#include <cstdint>

#include "ortools/graph/min_cost_flow.h"```

### Java

```import com.google.ortools.Loader;

### C#

```using System;

### Declare the solver

To solve the problem, we use the SimpleMinCostFlow solver.

### Python

```# Instantiate a SimpleMinCostFlow solver.
min_cost_flow = pywrapgraph.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();```

### Define the data

The following code defines the data for the problem. In this case, there are four arrays for the start nodes, end nodes, capacities, and unit costs. Again, the length of the arrays is the number of arcs in the graph.

### Python

```# 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.
start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]

# Define an array of supplies at each node.
supplies = [20, 0, 0, -5, -15]```

### 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.
std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
std::vector<int64_t> supplies = {20, 0, 0, -5, -15};```

### Java

```// 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
int[] supplies = new int[] {20, 0, 0, -5, -15};```

### 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };

// Define an array of supplies at each node.
int[] supplies = { 20, 0, 0, -5, -15 };```

For each start node and end node, we create an arc from start node to end node with the given capacity and unit cost, using the method AddArcWithCapacityAndUnitCost.

The solver's SetNodeSupply method creates a vector of supplies for the nodes.

### Python

```# Add each arc.
for arc in zip(start_nodes, end_nodes, capacities, unit_costs):
arc)

for count, supply in enumerate(supplies):
min_cost_flow.SetNodeSupply(count, supply)```

### C++

```// Add each arc.
for (int i = 0; i < start_nodes.size(); ++i) {
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}

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) {
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}

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 =
if (arc != i)
throw new Exception("Internal error");
}

for (int i = 0; i < supplies.Length; ++i)
{
minCostFlow.SetNodeSupply(i, supplies[i]);
}```

### Invoke the solver

Now that all the arcs have been defined, all that remains is to invoke the solver and display the results. We invoke the `Solve()` method.

### Python

```# Find the min cost flow.
status = min_cost_flow.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();```

### Display the results

Now, we can display the flow and cost across each arc.

### Python

```if status != min_cost_flow.OPTIMAL:
print('There was an issue with the min cost flow input.')
print(f'Status: {status}')
exit(1)
print('Minimum cost: ', min_cost_flow.OptimalCost())
print('')
print(' Arc   Flow / Capacity  Cost')
for i in range(min_cost_flow.NumArcs()):
cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
print('%1s -> %1s    %3s   / %3s   %3s' %
min_cost_flow.Flow(i), min_cost_flow.Capacity(i), cost))```

### C++

```if (status == MinCostFlow::OPTIMAL) {
LOG(INFO) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
LOG(INFO) << " Arc   Flow / Capacity  Cost";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
<< "  " << min_cost_flow.Flow(i) << "  / "
<< min_cost_flow.Capacity(i) << "       " << cost;
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
<< status;
}```

### Java

```if (status == MinCostFlow.Status.OPTIMAL) {
System.out.println("Minimum cost: " + minCostFlow.getOptimalCost());
System.out.println();
System.out.println(" Edge   Flow / Capacity  Cost");
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + "  "
+ minCostFlow.getFlow(i) + "  / " + minCostFlow.getCapacity(i) + "       " + cost);
}
} 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("Minimum cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
Console.WriteLine(" Edge   Flow / Capacity  Cost");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + "  " +
string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
string.Format("{0,3}", cost));
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
}```

Here is the output of the Python program:

```Minimum cost: 150

Arc    Flow / Capacity  Cost
0 -> 1    12  /  15        48
0 -> 2     8  /   8        32
1 -> 2     8  /  20        16
1 -> 3     4  /   4         8
1 -> 4     0  /  10         0
2 -> 3    12  /  15        12
2 -> 4     4  /   4        12
3 -> 4    11  /  20        22
4 -> 2     0  /   5         0
```

### Complete programs

Putting it all together, here are the complete programs.

### Python

```"""From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1."""
from ortools.graph import pywrapgraph

def main():
"""MinCostFlow simple interface example."""
# Instantiate a SimpleMinCostFlow solver.
min_cost_flow = pywrapgraph.SimpleMinCostFlow()

# 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.
start_nodes = [0, 0, 1, 1, 1, 2, 2, 3, 4]
end_nodes = [1, 2, 2, 3, 4, 3, 4, 4, 2]
capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5]
unit_costs = [4, 4, 2, 2, 6, 1, 3, 2, 3]

# Define an array of supplies at each node.
supplies = [20, 0, 0, -5, -15]

for arc in zip(start_nodes, end_nodes, capacities, unit_costs):
arc)

for count, supply in enumerate(supplies):
min_cost_flow.SetNodeSupply(count, supply)

# Find the min cost flow.
status = min_cost_flow.Solve()

if status != min_cost_flow.OPTIMAL:
print('There was an issue with the min cost flow input.')
print(f'Status: {status}')
exit(1)
print('Minimum cost: ', min_cost_flow.OptimalCost())
print('')
print(' Arc   Flow / Capacity  Cost')
for i in range(min_cost_flow.NumArcs()):
cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i)
print('%1s -> %1s    %3s   / %3s   %3s' %
min_cost_flow.Flow(i), min_cost_flow.Capacity(i), cost))

if __name__ == '__main__':
main()```

### C++

```// From Bradley, Hax and Maganti, 'Applied Mathematical Programming', figure 8.1
#include <cstdint>

#include "ortools/graph/min_cost_flow.h"

namespace operations_research {
// MinCostFlow simple interface example.
void SimpleMinCostFlowProgram() {
// 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.
std::vector<int64_t> start_nodes = {0, 0, 1, 1, 1, 2, 2, 3, 4};
std::vector<int64_t> end_nodes = {1, 2, 2, 3, 4, 3, 4, 4, 2};
std::vector<int64_t> capacities = {15, 8, 20, 4, 10, 15, 4, 20, 5};
std::vector<int64_t> unit_costs = {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
std::vector<int64_t> supplies = {20, 0, 0, -5, -15};

for (int i = 0; i < start_nodes.size(); ++i) {
start_nodes[i], end_nodes[i], capacities[i], unit_costs[i]);
if (arc != i) LOG(FATAL) << "Internal error";
}

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) << "Minimum cost flow: " << min_cost_flow.OptimalCost();
LOG(INFO) << "";
LOG(INFO) << " Arc   Flow / Capacity  Cost";
for (std::size_t i = 0; i < min_cost_flow.NumArcs(); ++i) {
int64_t cost = min_cost_flow.Flow(i) * min_cost_flow.UnitCost(i);
LOG(INFO) << min_cost_flow.Tail(i) << " -> " << min_cost_flow.Head(i)
<< "  " << min_cost_flow.Flow(i) << "  / "
<< min_cost_flow.Capacity(i) << "       " << cost;
}
} else {
LOG(INFO) << "Solving the min cost flow problem failed. Solver status: "
<< status;
}
}

}  // namespace operations_research

int main() {
operations_research::SimpleMinCostFlowProgram();
return EXIT_SUCCESS;
}```

### Java

```// From Bradley, Hax, and Maganti, 'Applied Mathematical Programming', figure 8.1.

/** Minimal MinCostFlow program. */
public class SimpleMinCostFlowProgram {
public static void main(String[] args) throws Exception {
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();

// 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = new int[] {0, 0, 1, 1, 1, 2, 2, 3, 4};
int[] endNodes = new int[] {1, 2, 2, 3, 4, 3, 4, 4, 2};
int[] capacities = new int[] {15, 8, 20, 4, 10, 15, 4, 20, 5};
int[] unitCosts = new int[] {4, 4, 2, 2, 6, 1, 3, 2, 3};

// Define an array of supplies at each node.
int[] supplies = new int[] {20, 0, 0, -5, -15};

for (int i = 0; i < startNodes.length; ++i) {
startNodes[i], endNodes[i], capacities[i], unitCosts[i]);
if (arc != i) {
throw new Exception("Internal error");
}
}

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("Minimum cost: " + minCostFlow.getOptimalCost());
System.out.println();
System.out.println(" Edge   Flow / Capacity  Cost");
for (int i = 0; i < minCostFlow.getNumArcs(); ++i) {
long cost = minCostFlow.getFlow(i) * minCostFlow.getUnitCost(i);
System.out.println(minCostFlow.getTail(i) + " -> " + minCostFlow.getHead(i) + "  "
+ minCostFlow.getFlow(i) + "  / " + minCostFlow.getCapacity(i) + "       " + cost);
}
} else {
System.out.println("Solving the min cost flow problem failed.");
System.out.println("Solver status: " + status);
}
}

private SimpleMinCostFlowProgram() {}
}```

### C#

```// From Bradley, Hax, and Magnanti, 'Applied Mathematical Programming', figure 8.1.
using System;

public class SimpleMinCostFlowProgram
{
static void Main()
{
// Instantiate a SimpleMinCostFlow solver.
MinCostFlow minCostFlow = new MinCostFlow();

// 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.
// Problem taken From Taha's 'Introduction to Operations Research',
// example 6.4-2.
int[] startNodes = { 0, 0, 1, 1, 1, 2, 2, 3, 4 };
int[] endNodes = { 1, 2, 2, 3, 4, 3, 4, 4, 2 };
int[] capacities = { 15, 8, 20, 4, 10, 15, 4, 20, 5 };
int[] unitCosts = { 4, 4, 2, 2, 6, 1, 3, 2, 3 };

// Define an array of supplies at each node.
int[] supplies = { 20, 0, 0, -5, -15 };

for (int i = 0; i < startNodes.Length; ++i)
{
int arc =
if (arc != i)
throw new Exception("Internal error");
}

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("Minimum cost: " + minCostFlow.OptimalCost());
Console.WriteLine("");
Console.WriteLine(" Edge   Flow / Capacity  Cost");
for (int i = 0; i < minCostFlow.NumArcs(); ++i)
{
long cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);
Console.WriteLine(minCostFlow.Tail(i) + " -> " + minCostFlow.Head(i) + "  " +
string.Format("{0,3}", minCostFlow.Flow(i)) + "  / " +
string.Format("{0,3}", minCostFlow.Capacity(i)) + "       " +
string.Format("{0,3}", cost));
}
}
else
{
Console.WriteLine("Solving the min cost flow problem failed. Solver status: " + status);
}
}
}```
[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]