Algorithms for the set covering problem
Angela Margaret Hey · Spiral (Imperial College London) · 1981
Solution methods .for the set covering problem, SCP, are the subject of this thesis.This problem is widely encountered, notably in operational research, computer science and electrical engineering.A survey of applications and algorithms is given in the 'first chapter.Heuristic algorithms that obtain upper and lower bounds on the optimal solution value' are given in Chapter 2. The SCP can be formulated as an integer program and one of the more successful approaches to this type of problem is Lagrangean relaxation embedded \ in a branch and bound (tree search) strategy.Chapter 3 illustrates techniques for efficiently increasing lower bounds obtained from Lagrangean relaxations.Lower tjounds to the SCP are derived using network flow and graph theory in Chapters 4 and 5. Chapter 6 discusses decomposition and state space relaxations for obtaining lower bounds to the SCP.Branching strategies are considered in Chapter 7. The implementation of.an algorithm for the SCP using the graph covering relaxations is given in Chapter 8. Conclusions, together with ideas for future research, are given in the final chapter.