Network flow: a powerful tool for modelling problems
November 1st, 2019Network flow is part of the graph theory toolbox, used to model transportation networks, scheduling, and resource matching. With today's libraries, a simple method call solves the optimisation — the hard part is modelling the problem correctly.
From unique paths to bipartite matching
Given a graph, finding unique (edge-disjoint) paths from node i to j is solved by setting each edge capacity to 1 and running maximum flow. For node-disjoint paths, duplicate every node into k and k' with capacity-1 edges between them. For employee-project matching: connect source to employees, employees to matching projects (based on skill requirements), and projects to sink. Set all edges to capacity 1. Maximum flow gives the optimal matching.
Extending with real-world constraints
Real problems have additional constraints: employee seniority ranks, project difficulty levels, budget limits. We modelled this with edge capacities equal to wages, source-to-worker edges based on simultaneous project capacity, and project-to-sink edges capped at project budget. Running max-flow-min-cost with networkx and filtering unsaturated edges gives budget-respecting assignments. — Armando
Explore more
Dealing with Optimisation Problems: FitJSP
How we used genetic algorithms to solve a job-shop scheduling problem and built a drag-and-drop online tool for interactive schedule management.
Smart Monitoring: Predictive Maintenance and Anomaly Detection Explained
We built a smart monitoring dashboard for Fednot using Azure Databricks, Anomaly Detector API, and Power BI — turning unstructured log files into predictive maintenance insights.
AI and RPA for an automated sales order process
How AI and robotic process automation can automate repetitive tasks like sales order entry, demonstrated through an AI assistant called Raphael.
Related Cases
Governed Databricks data platform for global operations
Volvo Logistics distributes over 700,000 spare parts worldwide. We built a governed Databricks data platform that unified operational data from six global sites — delivering up to 40% efficiency gains, 99% reduction in pipeline latency, and self-service analytics for business users.
Automating parcel label extraction
Automating parcel label extraction at Latvian Post — using Azure Form Recognizer and computer vision to liberate 2,000+ hours of manual work per month by automatically reading and completing missing parcel data.
