Surrogate constraint normalization for the set covering problem

The set covering problem (SCP) is central in a wide variety of practical applications for which finding good feasible solutions quickly (often in real-time) is crucial. Surrogate constraint normalization is a classical technique used to derive appropriate weights for surrogate constraint relaxations in mathematical programming. This framework remains the core of the most effective constructive heuristics for the solution of the SCP chiefly represented by the widely-used Chvatal method. This paper introduces a number of normalization rules and demonstrates their superiority to the classical Chvatal rule, especially when solving large scale and real-world instances. Directions for new advances on the creation of more elaborate normalization rules for surrogate heuristics are also provided. (C) 2010 Elsevier By. All rights reserved.