Network Flow - min-cost flow

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

Show code

import { initNetworkFlow, SimpleMinCostFlow, setWorkerBridgeEnabled } from 'or-tools-wasm/network-flow';

setWorkerBridgeEnabled(true);
await initNetworkFlow();

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.add_arcs_with_capacity_and_unit_cost(
  startNodes,
  endNodes,
  capacities,
  unitCosts,
);
minCostFlow.set_nodes_supplies([0, 1, 2, 3, 4], supplies);

const status = await minCostFlow.solve();
if (status === SimpleMinCostFlow.OPTIMAL) {
  console.log(minCostFlow.optimal_cost(), minCostFlow.maximum_flow());
  console.log(allArcs.map((arc) => ({
    tail: minCostFlow.tail(arc),
    head: minCostFlow.head(arc),
    capacity: minCostFlow.capacity(arc),
    cost: minCostFlow.unit_cost(arc),
    flow: minCostFlow.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.

Use worker bridge Supply nodes Transit nodes Demand nodes

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: