Abstract: Lp relaxation of Ip problems usually provides good bounds on the objective function value IP problems, including SCP problems. Although, these bounds are strong they are time consuming and are not suitable to be used in a tree search algorithm. Quick and relatively strong bounds for IP problems have their own attractions. In this study, a new way is proposed to impose side constraints to a graph theoretic relaxation of SCP. Shortest Route Relaxation (SRR) of the Set Covering Problem (SCP) is upgraded by the reallocation of the column costs for some columns of the A matrix. This method is called Residual Cost Algorithm (RCA). This algorithm is applied to a strong cost allocation strategy. It is shown that the lower bound of the SCP is increased for a number of standard test problems and computational results are presented.