Editing Max-flow min-cut theorem (section)

===Project selection problem===
[[File:Max-flow min-cut project-selection.svg|thumb|right|A network formulation of the project selection problem with the optimal solution]]
In the project selection problem, there are {{mvar|n}} projects and {{mvar|m}} machines. Each project {{mvar|p<sub>i</sub>}} yields revenue {{math|''r''(''p<sub>i</sub>'')}} and each machine {{mvar|q<sub>j</sub>}} costs {{math|''c''(''q<sub>j</sub>'')}} to purchase. We want to select a subset of the project, and purchase a subset of the machines, to maximize the total profit (revenue of the selected projects minus cost of the purchased machines). We must obey the following constraint: each project specifies a set of machines which must be purchased if the project is selected. (Each machine, once purchased, can be used by any selected project.)

To solve the problem, let {{mvar|P}} be the set of projects ''not'' selected and {{mvar|Q}} be the set of machines purchased, then the problem can be formulated as,

:<math>\max \{g\} = \sum_{i} r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j).</math>

Since the first term does not depend on the choice of {{mvar|P}} and {{mvar|Q}}, this maximization problem can be formulated as a minimization problem instead, that is,

:<math>\min \{g'\} = \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j).</math>

The above minimization problem can then be formulated as a minimum-cut problem by constructing a network, where the source is connected to the projects with capacity {{math|''r''(''p<sub>i</sub>'')}}, and the sink is connected by the machines with capacity {{math|''c''(''q<sub>j</sub>'')}}. An edge {{math|(''p<sub>i</sub>'', ''q<sub>j</sub>'')}} with ''infinite'' capacity is added if project {{mvar|p<sub>i</sub>}} requires machine {{mvar|q<sub>j</sub>}}. The s-t cut-set represents the projects and machines in {{mvar|P}} and {{mvar|Q}} respectively. By the max-flow min-cut theorem, one can solve the problem as a [[maximum flow problem]].

The figure on the right gives a network formulation of the following project selection problem:

{| class="wikitable" style="text-align:center; width:500px;" border="1"
|-
! width="20px" |
! width="100px" |
Project {{math|''r''(''p<sub>i</sub>'')}}
! width="100px" |
Machine {{math|''c''(''q<sub>j</sub>'')}}
!
|-
! 1
| 100 || 200
| align="left" style="padding-left: 1em;" |
Project 1 requires machines 1 and 2.
|-
! 2
| 200 || 100
| align="left" style="padding-left: 1em;" |
Project 2 requires machine 2.
|-
! 3
| 150 || 50
| align="left" style="padding-left: 1em;" |
Project 3 requires machine 3.
|}

The minimum capacity of an s-t cut is 250 and the sum of the revenue of each project is 450; therefore the maximum profit ''g'' is 450 − 250 = 200, by selecting projects {{math|''p''<sub>2</sub>}} and {{math|''p''<sub>3</sub>}}.

The idea here is to 'flow' each project's profits through the 'pipes' of its machines. If we cannot fill the pipe from a machine, the machine's return is less than its cost, and the min cut algorithm will find it cheaper to cut the project's profit edge instead of the machine's cost edge.