Synthesis of 2-commodity flow networks. (English) Zbl 1082.90012
Summary: We investigate network design under volatile conditions of link failures and traffic overload. Our model is a nonsimultaneous 2-commodity problem. We characterize the feasible solutions and, using this characterization, we reduce the size of the linear program. For \(0/1\) requirements we present a closed fractional optimal solution, a closed integer-capacities optimal solution, and \(7/6\)-approximation for the case in which integer 2-commodity flows are required.
MSC:
90B15 | Stochastic network models in operations research |
90C27 | Combinatorial optimization |
90C59 | Approximation methods and heuristics in mathematical programming |