A combinatorial arc tolerance analysis for network flow problems. (English) Zbl 1213.90075

Summary: For the separable convex cost flow problem, we consider the problem of determining a tolerance set for each arc cost function. For a given optimal flow \(x\), a valid perturbation of \(c_{ij}(x)\) is a convex function that can be substituted for \(c_{ij}(x)\) in the total cost function without violating the optimality of \(x\). Tolerance set for an \(\text{arc}(i,j)\) is the collection of all valid perturbations of \(c_{ij}(x)\). We characterize the tolerance set for each \(\text{arc}(i,j)\) in terms of nonsingleton shortest distances between nodes \(i\) and \(j\). We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in \(O(n^3)\) time where \(n\) denotes the number of nodes in the given graph.


90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
Full Text: DOI EuDML