Innovative Cost Allocation Strategies for the Shortest Route Relaxation of the Set Covering Problem


Bahar Obed Ali and Farhad Djannaty




Graph theoretic relaxation of the Set Covering Problem (SCP) is an alternative way of relaxing the problem to obtain quick lower bounds on the value of the objective function. A number of new cost allocation strategies are introduced for the shortest route relaxation of the SCP problem which takes advantage of the specific knowledge of the problem. These strategies are applied to a number of standard test problems and computational results are presented.


Int. J. Contemp. Math. Sciences, Vol. 7, 2012, no. 9, 425–438