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

Authors: Gary W. Kinney, J. Wesley Barnes, Bruce W. Colletti

Addresses: Department of Operational Sciences, Air Force Institute of Technology, Wright-Patterson AFB, OH 45433-7765, USA. ' Graduate Program in Operations Research and Industrial Engineering, The University of Texas at Austin, Austin, TX 78712, USA. ' Analytic Services Inc., P.O. Box 6370, Arlington VA 22206, USA

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

Keywords: combinatorial optimisation; heuristics; tabu search; reactive TS; LP relaxation; variable clustering; landscape partitioning; set covering problem; unicost SCP; operational research; linear programming.

DOI: 10.1504/IJOR.2007.012458

International Journal of Operational Research, 2007 Vol.2 No.2, pp.156 - 172

Published online: 14 Feb 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article