Adjusting an infeasible network by minimizing the sum of the violation costs

作者：Ghiyasvand M

来源：Scientia Iranica, 2017, 24(1): 319-329.

DOI：10.24200/sci.2017.4036

• Infeasible network
• The cost scaling algorithm
• The minimum cost flow problem
• Parallel arcs
• Convex cost

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 as the adjusting problem and show that it is transformed to a minimum cost flow problem on a special parallel network. Thus, the adjusting problem is solved using minimum cost flow algorithms. 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 a way which performs fewer operations than our first implementation.

• 出版日期2017-2