This new scaling algorithm (Fathabadi scaling algorithm) solve the feasibility problem of a network flow. It determines whether a network feasible or not using conservation and boundedness constraints. If the network is infeasible then algorithm finds a positive cut. It also repair an infeasibile network and estimate the maximum cost of repairing. For a network with n nodes and m arcs, the algorithm running time O(m²log(nU)). Where U is the largest absolute arc bounds. This algorithm was published in 2007 Elsevier Inc by Hassan Salehi Fathabadi and Mehdi Ghiyasvand.

For this algorithm,we assume that the lower and upper capacity bounds are integer. In each iteration, the algorithm call a procedure of searching a δ feasible flow. Suppose that D =(N, A) is a network with node set N, arc set A, lower bounds l, upper bounds u. Then we can say the network D is feasible if there exists a flow x satisfying following constraints (1) and (2):

             ∑xji  - ∑xij = 0   for all i ∈ N       (conservation)             (1)
            jєN     jєN
             lij ≤ xij ≤ uij   for all i ∈ N         (boundedness)              (2)

Algorithm relaxes the capacity bound by δ of the network; that means , it takes (l_ij - δ , u_ij + δ) instead of (l_ij , u_ij ) for each arc i → j. Such network is called a δ network. By Hoffman's theorem "A network with conservation and boundedness constrains is feasible if and only if for every cut (S, T), we have V (S,T)≤ 0". A cut (S, T) with V (S,T) > 0 is called a positive cut. Let x be input to the procedure of searching a δ-feasible flow, thus it is a 2δ-feasible flow. Let G = G⁺ U G^-

such that:

G⁺ = {i → j ∈ A | u_ij + δ < x_ij ≤ u_ij + 2δ },

G^- = {i → j ∈ A | u_ij < x_ij ≤ u_ij + δ }.
Let B = B⁺ U B^-
such that:

B⁺ = {i → j ∈ A | l_ij - 2δ < x_ij ≤ l_ij - δ },

B^- = {i → j ∈ A | l_ij - δ < x_ij ≤ l_ij }.
also let
R = {i → j ∈ A | l_ij ≤ x_ij ≤ u_ij },

Theorem 1: Let D=(N, A) be a graph whose arcs are divided into three sets B, G and R. Assume that a₀ ∈ B(resp. a₀ ∈ G) then one of the following cases applies:

(a) A simple cycle C containing a₀ exists such that all arcs of C that are in the set B have the same (resp. opposite)direction as a₀ and all arcs of C that are in G have a opposite (resp. same) direction to a₀. (Call C a colored-cycle)

(b) A cut (W, Z), which contains arc a₀ and does not contain the arcs of R, exists such that all arcs of (W, Z) are in the set G and all arcs of (W, Z)are in the set B, i.e. if i → j ∈ (W, Z) then i → j ∈ G and if i → j ∈ (W, Z) then i → j ∈ B (call (W, Z) a colored-cut).
Lemma 1 Removing arc w → v from the set B⁺ U G⁺
Assume that we have a colored cycle C containing an arc w → v ∈ B⁺ U G⁺. We augment the flow along C by δ units as follows. First consider the following cases which are true. Case (a): i → j ∈ B^-, if we let x^'_ij = x_ij + δ then i → j ∉ B⁺ U G⁺
Case (b): i → j ∈ G^-, if we let x^'_ij = x_ij - δ then i → j ∉ B⁺ U G⁺
Case (c):i → j ∈ R^-, if we let x^'_ij = x_ij + δ or x^'_ij = x_ij - δ then i → j ∉ B⁺ U G⁺
Case (d): i → j ∈ B⁺, if we let x^'_ij = x_ij + δ then i → j ∉ B⁺ U G⁺
Case (e): i → j ∈ G⁺, if we let x^'_ij = x_ij - δ then i → j ∉ B⁺ U G⁺
by cases (a, b, c), any arc i → j ∈ B^- U G^- U R of the colored-cycle C will not enter into B⁺ U G⁺. Also by cases (d, e) the arc w → v will be entered into the set B^- U G^- U R (i.e. w → v ∉ B⁺ U G⁺). because flow is changed along a cycle, Eq. (1) are maintained.

Scaling algorithm to solve the feasibility problem:
begin
let x = 0 and δ = U;
do until δ < 1/m;
begin
let δ := δ/2;
Searching a δ-feasible flow (δ,x);
end
end

begin
Define B⁺, B^-, G⁺, G^- and R as above
1 do until B⁺ U G⁺ ≠ Φ

     begin

     select arc w → v ∈ B+U G+;

     do the labeling procedure of the theorem 1;

     if we have a colored-cycle containing w → v;

     then

     begin

     adjust x by the Lemma 1;

     update B, R and G;

     goto 1;

     end;

     else goto 2;

2 let (W, Z)be the colored-cut containing w → v;

     write (W, Z) "is a positive cut and the network is infeasible";

     break;

     end;

  end;


     
          

The running time of the procedure of searching a δ-feasible flow is O(m²). As an arc moves out from B⁺ U G⁺ it will never come back to this set in the next iterations, and |B⁺ U G⁺| ≤ m, therefore the number of iterations is at most m. In each iteration, the searching procedure identify an arc as colored-cycle or colored-cut. This process takes O(m) times (by a breadth-first search). Thus the time order of the procedure is O(m²). The number of overall iterations is O(log(nU)). But in each iteration, the algorithm call the procedure of searching a δ-feasible flow. Therefore, the running time of the algorithm is O(m²log(nU)).

By the algorithm, we can convert an infeasible network to a feasible network. Suppose δ-network is feasible but δ/2 network is infeasible. If we increase u_ij and decrease l_ij by δ then the new network will be feasible. Thus for repairing a network maximum changes will be 2mδ. Assume that a network with demand d = 0. But we have d_i ≠ 0 for some node i. Then we have to add a new node with d_o = 0. Now for each node i with d_i > 0, add an arc i→o and also add an arc o→i for each node i with d_i < 0 such that l_io = u_io = d_i and l_oi = u_oi = - d_i respectively. Then reset all d_i =0. As a result, we will get a new feasible network if and only the original network is feasible. Now we can apply our algorithm on new feasible network.

This scaling algorithm can be used to solve the following problems, among others

• Bipartite matching
  
• Transportation problem
  
• Network connectivity
  

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flow: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, NJ,1993.

[2] R.K. Ahuja, J.B. Orlin, R.E. Tarjan, Improved time bounds for the maximum flow problem, SIAM J. Comput. 18 (1989) 939–954.

[3] M. Ghiyasvand, A new approach for computing a most positive cut using the minimum flow algorithms, Appl. Math. Comput. 176 (2006) 27–36.

[4] A.V. Goldberg, S. Rao, Beyond the flow decomposition barrier, J. ACM 45 (1988) 735–797.

[5] A.V. Goldberg, R.E. Tarjan, A new approach to the maximum flow problem, J. ACM 35 (1998) 921–940.

[6] R. Hassin, The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm, Math. Program. 25 (1983) 228–239.

[7] R. Hassin, Algorithm for the minimum cost circulation problem based on maximizing the mean improvement, Oper. Res. Lett. 12 (1992) 228–239.

[8] A.J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in: R. Bellman, M.Hall Jr., (Eds.), Proceedings of the Symposia in Applied Mathematics, vol. X Combinatorial Analysis, American Mathematical Society, Providence RI, 1960, pp. 113–127.

[9] v. King, S. Rao, R. Tarjan, A faster deterministic maximum flow algorithm, J. Algorithms 17 (1994) 447–474.

[10] S.T. McCormick, T.R. Ervolina, Computing maximum mean cuts, Discret. Appl. Math. 52 (1994) 53–70.

[11] S. Phillips, J. Westbrook, Online load balancing and network flow, in: Proc. 25th Ann. ACM Symposium on Theory of Comput., 1993, pp. 402–411.

[12] Hassan SalehiFathabadi, Mehdi Ghiyasvand, A new algorithm for solving the feasibility problem of a network flow, ISSN 0096-3003, 2007, Volume 192, Issue 2, pp. 429 - 438.