A Reactive Tabu Search algorithm with variable clustering for the Unicost Set Covering Problem

摘要

We develop a Reactive Tabu Search (RTS) algorithm for solving the Unicost Set Covering Problem (SCP) - USCP-TS. We solve a Linear Programming (LP) relaxation of the problem and use the LP optimum to construct a quality solution profile. We cluster the problem variables based on this profile and partition the solution space into orbits. We tested our algorithm on 65 benchmark proble ns and compared the results against the previous best-known solutions and ihose obtained by CPLEX 9.0 under varied settings. USCP-TS outperforms CPLEX in solution quality for 32 of the problems and achieves the same solution as CPLEX faster on 21 of the remaining problems.