CODEWITHSUNDEEP
algorithmlinear-programmingnetwork-flow
user3070752
user3070752

Reputation: 734

how to use network flow to solve linear programming?

suppose we are given m examination E={E1,E2,...,Em} and a set of instruments of I={I1,I2,...,In} and each examination Ej needs a subset of Rj of I. each examination has Pj $ profit and each instrument costs Cj $. we want to choose some examination to maximize (sum of profits - sum of costs).

I think we can use LP such that we have m variable Xi for each examination and Xi = 0 or 1 and our objective function is : for all i and j Xi(Pi) - (A)Cj where A is xor all Xi that need Ij

but i can't model this problem by network flow. my problem is how to represent the fact that when we choose an examination and pay for its instruments we can use those instruments for other examination.

Upvotes: 2

Views: 309

Answers (1)

Niklas B.
Niklas B.

Reputation: 95308

Model the problem as a bipartite graph: put the examinations as vertices on the left side and the instruments on the right side. Connect examinations to their instruments via edges of infinite capacity. Now introduce a source S and a sink T. Connect S to the examinations via edges that represent their profit. Connect the instruments to T via edges representing their cost.

The maximum profit is sum of all Pi - min cut.

Why? Think about cutting edges in the graph to separate T from S. For each examination, we need to cut either the examination itself, "paying" for the profit we missed, or all of its instruments.

An optimal set of examinations is represented by the set of examination vertices reachable from S in the residual flow network.

Upvotes: 3

Related Questions