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. |