Project Selection Problem
There are N projects.
- Doing project i yields income [$ r_i
There are m machines.
- Buying machine j costs [$ c_j
In order to do a project, you have to buy the machinery needed for that project.
Which project should I choose to maximize profit = revenue - cost?
Solvable by minimum cut ( maximum flow)
Easier to understand if interpreted as vertex painting
The project painted in the same color as the start is the "selected project"
Machines painted the same color are "purchased machines."
In the figure, -p should be read as r
The following explanation is Cutting the smallest cut is not "cutting an edge". This is not a good explanation because it was written before I understood
There are N projects.
There are m machines.
Project requires some machinery
Choosing project pi yields income r(pi)
Buying the required machine qj costs c(qj)
Which project should I choose to maximize profit-cost?
- Solvable by minimum cut ( maximum flow)
Express the constraint, "If a project is selected, we must buy the necessary machinery," with the edge of infinity
- Either the right or left side must be cut.
- View not cutting the project edge as a "project choice".
- Cutting the edge of a machine is viewed as "buying a machine".
- If you have selected a project (not cutting an edge), you need to buy a machine (cutting an edge).
- Not choosing a project = less income, buying a machine = cost, want to minimize this sum -> minimum cut
It can be interpreted as a question of choosing between two options. - LP, Graphs and Formulations
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem
This page is auto-translated from [/nishio/Project Selection Problem](https://scrapbox.io/nishio/Project Selection Problem) using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.