What is the network flow problem that corresponds to this project selection problem?

user_3977145 0
Viewed 356

This question is about the Application of Network Flows to Project Selection. The project selection problem is the problem of which set of projects to select to maximise revenue. Each project has a revenue (positive or negative). Projects also have prerequisites which are other projects. A set of projects A is feasible if the prerequisite of every project in A is also in A. The project selection problem is to choose a feasible set of projects with maximal revenue. A project selection problem can be transformed into a Network Flow problem, and solved using the Ford Fulkerson algorithm. Consider the following set of projects:

Name, Revenue, Pre-requisites

A, 6, D

B, 9, D

C,-8

D, -12

E, 7, C D

I am confused here as C and D have negative revenues and I am not sure how to reduce this problem to a network flow problem.

network-flow algorithm
1 Answers

It's easier to think about reducing this problem to max flow's dual problem, min cut, since each cut is defined by a subset of nodes. Given a max flow from (e.g.) Ford--Fulkerson, we can find a min cut by performing a depth-first search from the source in the residual graph.

Since we want to choose a subset of projects, most of the nodes in the network correspond to a project, with the exception of a source node and a sink node. The projects chosen will be the ones on the source side of the min cut. For each project u that depends on a project v, we add an infinite (or very large) capacity arc from u to v, so that every cut that includes u but not v has infinite capacity, putting it out of contention.

Now we get to the heart of your question: dealing with revenue (profit, really, but I'll match your terminology) that may be positive, negative, or zero. Given that we're working with min cuts, we want to minimize minus revenue, since that's equivalent to maximizing revenue. For projects with negative revenue we set a cost for including them by adding an arc with capacity equal to minus the negative revenue from the project node to the sink. We pay this cost if and only if the project node is on the source side, i.e., the project is chosen. For projects with positive revenue, we add an arc from the source to the project node with capacity equal to revenue. This biases the objective in the sense that the min cut is no longer equal to the total revenue, but they differ only by an additive constant, and the mechanism has the correct effect in that, if we don't choose the project, then we add its revenue to the min cut.

user_21446690
Related