Investments in stochastic maximum flow networks

Each are (i, j) of the network has capacity _ij where _ij is a non-negative random variable. The capacity of any arc may be reduced increased by an amountu _ij 0 at a cost ofc _ij u _ij . The objective is to maximizev–Kc _ij u _ij wherev is the expected maximum flow. This problem is formulated as a two-stage linear program under uncertainty. Each feasible generates a constraint where is the probability arc (i, j) is in the minimum cut set and the expected value of the maximum flow under . The formulation is later generalized to include certain conditions under which the increase in capacity of an arc may be a non-deterministic function of the investmentc _ij u _ij .