×

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
Full Text: DOI