Adjusting an Infeasible Network by Minimizing the Sum of the Violation Costs

Abstract

In this paper, for a given infeasible network, we change the lower and upper bounds such that the sum of the violations costs from the lower and upper bounds is minimum. We call this problem the adjusting problem and show it is transformed to a minimum cost flow problem on a parallel network. Thus, the adjusting problem can be solved using any minimum cost flow algorithm on a parallel network. Solving a minimum cost flow problem with parallel arcs, in practice, is complicated and needs more time in comparison with a minimum cost flow problem without parallel arcs. If the parallel arcs are eliminated then we achieve substantial saving in the storage requirements, which translates into enhanced speed of algorithms. One of the best algorithms to solve the minimum cost flow problem is the cost scaling algorithm of Goldberg and Tajan(1990). In this paper, we present two modified versions of their algorithm to solve the adjusting problem. In the first modification, in order to achieve an enhanced speed of algorithm, the parallel arcs are eliminated using an especial residual network. In the second modification, the adjusting problem is transformed to a convex cost flow problem and the cost scaling algorithm is modified in away which performs fewer operations than our first implementation.