Network Flow - linear sum assignment

Problem: assign every worker to one task so the total assignment cost is as small as possible; this is the classic Hungarian algorithm problem.

Show code

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

setWorkerBridgeEnabled(true);
await initNetworkFlow();

const costs = [
  [90, 76, 75, 70],
  [35, 85, 55, 65],
  [125, 95, 90, 105],
  [45, 110, 95, 115],
];

const leftNodes: number[] = [];
const rightNodes: number[] = [];
const arcCosts: number[] = [];
for (let worker = 0; worker < costs.length; ++worker) {
  for (let task = 0; task < costs[worker].length; ++task) {
    leftNodes.push(worker);
    rightNodes.push(task);
    arcCosts.push(costs[worker][task]);
  }
}

const assignment = new SimpleLinearSumAssignment();
assignment.add_arcs_with_cost(leftNodes, rightNodes, arcCosts);
const status = await assignment.solve();

if (status === SimpleLinearSumAssignment.OPTIMAL) {
  console.log(assignment.optimal_cost());
  for (let worker = 0; worker < assignment.num_nodes(); ++worker) {
    console.log(worker, assignment.right_mate(worker), assignment.assignment_cost(worker));
  }
}

Model

Each worker must be matched to exactly one task.
Each task must receive exactly one worker.
Every worker-task pair has an assignment cost.
The solver finds the one-to-one matching with minimum total cost.
The visualization highlights the selected worker-task pairs after solving.

Use worker bridge Size

Workers are green nodes and tasks are red nodes.
This is the linear assignment problem, commonly associated with the Hungarian algorithm.
Every worker can be matched to one task with a different cost.
Use Size and Randomize to generate a new square worker-task cost matrix.
The solver chooses one task per worker while minimizing total assignment cost.
After solving, selected matches are emphasized in the cost matrix.

Run the solver to view the assignment.

Status: