| Article ID: | iaor20073146 |
| Country: | United Kingdom |
| Volume: | 2 |
| Issue: | 2 |
| Start Page Number: | 156 |
| End Page Number: | 172 |
| Publication Date: | Feb 2007 |
| Journal: | International Journal of Operational Research |
| Authors: | Barnes J. Wesley, Colletti Bruce W., Kinney Gary W. |
| Keywords: | heuristics: tabu search, programming: linear |
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 problems and compared the results against the previous best-known solutions and those 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.