TY  - JOUR
T1  - Enhancing the Shortest Route Relaxation of the Set Covering Problem
AU - , Farhad Djannaty 
JO  - Journal of Modern Mathematics and Statistics
VL  - 1
IS  - 1
SP  - 30
EP  - 34
PY  - 2007
DA  - 2001/08/19
SN  - 1994-5388
DO  - jmmstat.2007.30.34
UR  - https://makhillpublications.co/view-article.php?doi=jmmstat.2007.30.34
KW  - Network relaxation
KW  -set covering
KW  -residual cost
KW  -shortest route rebxation
AB  - 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.
ER  -