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

Gary W. Kinney, J. Wesley Barnes and Bruce W. Colletti

International Journal of Operational Research, 2007, vol. 2, issue 2, 156-172

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. (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=12458 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:2:y:2007:i:2:p:156-172

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().