Project Selection Problem
What you'll learn: You'll learn how to model a project selection scenario—where some projects have profits, some have costs, and certain projects require others—as a maximum flow problem to find the most profitable subset of projects to undertake.
The Core Idea
Imagine you're a manager deciding which projects to green-light. Each project has an associated profit (or cost), and some projects have prerequisites: you can't do Project B unless you also commit to Project A. Your goal is to maximize total revenue by choosing the optimal set of projects.
This problem maps beautifully to a min-cut problem, which by the max-flow min-cut theorem, we solve using maximum flow algorithms.
Building the Flow Network
Here's how to construct the graph:
- Create a source node
sand a sink nodet - For each project
iwith positive profitp_i, add an edge fromsto nodeiwith capacityp_i - For each project
jwith costc_j(negative profit), add an edge from nodejtotwith capacityc_j - For each prerequisite relationship (project
jrequires projecti), add an edge fromjtoiwith infinite capacity
Why It Works
The minimum cut separates the source from the sink. Projects on the source side of the cut are selected; those on the sink side are rejected. The infinite-capacity edges ensure prerequisites are respected (cutting them would be infinitely expensive). The min-cut value represents the maximum profit we must forgo, so:
Maximum profit = (sum of all positive profits) - (min-cut value)
Key Takeaway: The project selection problem transforms business logic (profits, costs, dependencies) into a max-flow/min-cut problem, letting you compute the optimal project portfolio efficiently using flow algorithms like Edmonds-Karp or Dinic's.