TY - JOUR ID - 4036 TI - Adjusting an Infeasible Network by Minimizing the Sum of the Violation Costs JO - Scientia Iranica JA - SCI LA - en SN - 1026-3098 AU - Ghiyasvand, Mehdi AD - Bu-Ali Sina University Y1 - 2017 PY - 2017 VL - 24 IS - 1 SP - 319 EP - 329 KW - Operations research KW -   Optimizations KW - Network flows DO - 10.24200/sci.2017.4036 N2 -  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. UR - https://scientiairanica.sharif.edu/article_4036.html L1 - https://scientiairanica.sharif.edu/article_4036_2362151ff91818bc9e4c9ab39d98da0f.pdf ER -