Loading solver…

Network Flow - min-cost flow

Problem: move supply to demand through capacity-limited arcs while minimizing total unit shipping cost.

Show code 
import {
  SimpleMinCostFlow,
  SimpleMinCostFlowStatus,
} from 'or-tools-wasm/network-flow';

const startNodes = [0, 0, 1, 1, 1, 2, 2, 3, 4];
const endNodes = [1, 2, 2, 3, 4, 3, 4, 4, 2];
const capacities = [15, 8, 20, 4, 10, 15, 4, 20, 5];
const unitCosts = [4, 4, 2, 2, 6, 1, 3, 2, 3];
const supplies = [20, 0, 0, -5, -15];

const minCostFlow = new SimpleMinCostFlow();
const allArcs = minCostFlow.addArcsWithCapacityAndUnitCost(
  startNodes,
  endNodes,
  capacities,
  unitCosts,
);
minCostFlow.setNodesSupplies([0, 1, 2, 3, 4], supplies);

const result = await minCostFlow.solve({ executor: 'worker' });
if (result.status === SimpleMinCostFlowStatus.OPTIMAL) {
  console.log(result.optimalCost, result.maximumFlow);
  console.log(allArcs.map((arc) => ({
    tail: minCostFlow.tail(arc),
    head: minCostFlow.head(arc),
    capacity: minCostFlow.capacity(arc),
    cost: minCostFlow.unitCost(arc),
    flow: result.flow(arc),
  })));
}

Model

  • Supply nodes provide flow and demand nodes consume flow.
  • Transit nodes can pass flow along capacity-limited directed arcs.
  • Every arc has a per-unit cost and a maximum capacity.
  • The solver satisfies all demand at minimum total shipping cost.
  • After solving, arc labels show how much flow is sent on each chosen route.
  • Green nodes supply flow and red nodes demand flow.
  • Each arc has a capacity and a unit shipping cost.
  • The solver routes flow to satisfy demand with minimum total cost.
  • After solving, blue arc thickness shows shipped flow.
Run the solver to view the min-cost flow solution.

Status: