An algorithm for set covering problem.pdf

European Journal of Operational Research 31 (1987) 85-93 North-Holland An algorithm for set covering problem . BEASLEY Department of Management Science, Imperial College, London S W7 2BX, England Abstract: In this paper we present an algorithm for the set covering problem bines problem reduction tests with dual ascent, subgradient optimisation and linear programming. Computational results are presented for problems involving up to 400 rows and 4000 columns. Keywords: Set covering, optimisation 1. Introduction In this paper we consider the set covering prob- lem (SCP) which is the problem of covering the rows of a m-row, n-column, zero-one matrix ( aij) by a subset of the columns at minimum cost. Formally the problem can be defined as follows: Let xj = 1 if column j (cost cj) is in the solution, = 0 otherwise, then the program is minimise ,~~ subject to ,$r aijXj >, 1, i = 1,. . . , m, (2) E (O> l>> j=l ,**-, n. (3) Equation (2) ensures that each row is covered by at least one column and equation (3) is the in- tegrality constraint. If the inequalities in equation (2) are replaced by equalities the resulting prob- lem is called the set partitioning problem (SPP). Both the SCP and the SPP are well-known problems in the literature and have applications in The author would like to acknowledge the help of Egon Balas and Maria-Cecilia Carrera o