| Given a directed network with nonnegative arc capacities c ij and two specified nodes s and t, the maximum capacity s-t path (MCP) problem is to find a path P from s to t whose capacity is maximum, where the capacity of P is defined to be the minimum of the capacities of the arcs in P. The problem is sometimes called the maximin path problem or the bottleneck path problem. The MCP problem has applications in reliability theory, bicriteria optimization, and service routing. It also appears in a subroutine for some maximum flow algorithms.; We consider a more general problem in a stochastic network, where the arc capacities are random variables Cij, each assumed to have a known discrete distribution with finite support. The actual realizations are known only locally in the sense that we know Cij = cij only when we reach node i. The maximum capacity s-t path with recourse ( MCPR) problem is to find an optimal policy for choosing arcs, such that the expected capacity of the resulting s-t path is maximized. Our solution approach uses Markov decision processes (stochastic dynamic programming) and a version of the primal-dual method for linear programming. |
