Journal of Modern Mathematics and Statistics 
1 (1-4): 30-34, 2007 Enhancing the Shortest Route Relaxation of the Set Covering problem Farhad Djannaty 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 constrains to a graph theoretic relaxation of SCP. Shortest Route Relaxation (SRR) of the Set Covering Problem (SCP) is upgraded b reallocation of the column costs for some 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.